Difference Between Sum of Nodes at Odd Levels and Sum of Nodes at Even Levels of a Binary Tree Using Recursion

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.