# Binary Tree diff of sum of nodes at odd and sum of nodes at even

Given a Binary Tree, write a function which calculates the difference between the sum of node values at odd levels and sum of node values at even levels.
Consider the root node is at height 1.

The solution is short and uses recursion. The idea is that you negate all levels under the current one (the level of the current node) and you do that on each step of the recursion.
sum[l1] – (sum[l2] – (sum[l3] – (sum[l4] – … = sum[l1] – sum[l2] + sum[l3] – sum[l4]…

```int getDifference(Tree *root) {
if (root == null) {
return 0;
}
int result = root->data - geteDifference(root->left)
- getDifference(root->right);
return result;
}
```

### 4 Thoughts on “Binary Tree diff of sum of nodes at odd and sum of nodes at even”

1. Aniket Gaikwad on July 29, 2013 at 8:25 pm said:

2. crazyadmin on July 29, 2013 at 8:27 pm said:

Hi Aniket,

Here is the break down of the formula, where for example n1 is the node with value 1, and so on:
root->data – calc(root->left) – calc(root->right)=
5 – calc(n2) – calc(n6)=
5 – (2 – calc(n1) – calc(n4)) – (6 – 0 – calc(n8))=
//… skip a few rows
5 – (2 – (1 – 0 – 0) – (4 – 3)) – (6 – 0 – (8 – 7 – 9)) = -9

Hope this is clear..

3. win A VR headset on July 18, 2016 at 9:56 pm said:

A variety of terms have actually been made use oof to describe this:
crowd-sourcing, wisdom of crowds, peer production, wikinomics (Benkler, 2006; Howe, 2008; Surowiecki, 2004;
Tapscott andd Williams, 2006).

4. int diff_sum_nodes_odd_even(node *root, int multiplier) {
if (!root)
return 0;
else {
int sum = root->val*multiplier;
multiplier *= -1;
sum += diff_sum_nodes_odd_even(root->left,multiplier);
sum += diff_sum_nodes_odd_even(root->right,multiplier);
return sum;
}
}