Engineering Full Stack Apps with Java and JavaScript
Recursively substract the data values of child nodes from current node.
Assume the full and complete tree with levels as:
6
11
1111
This will become 6 - (1-1-1) - (1-1-1) => 6 - (-1) - (-1) => 6+1 + 1 => 8.
int getLevelDiff(TreeNode n)
{
if(n==null) return 0;
return (n.data - getLevelDiff(n.left) - getLevelDiff(n.right));
}
Time complexity will be O(n)
Space complexity will be O(log n) for recursive calls.
If we need to apply this for a generic tree (non-binary tree), we can do it as below assuming getChildren return a collection of trees that implements the Iterator interface:
int getLevelDiff(TreeNode n)
{
if(n==null) return 0;
int diffSum = n.data;for(TreeNode t: n.getChildren())
{
diffSum = diffSum - getLevelDiff(t);
}
return diffSum;
}
Complexities will be similar to that of the original solution.