JAVAJEE.COM
Engineering Full Stack Apps with Java and JavaScript
Difference Between Sum of Nodes at Odd Levels and Sum of Nodes at Even Levels of a Binary Tree Using Recursion
Normal Login
Approach
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.
Solution
int getLevelDiff(TreeNode n)
{
if(n==null) return 0;
return (n.data - getLevelDiff(n.left) - getLevelDiff(n.right));
}
Complexity
Time complexity will be O(n)
Space complexity will be O(log n) for recursive calls.
Solution for a non-binary tree
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.
- heartin's blog
- Log in or register to post comments