Given a binary tree, calculate the difference between sum of all nodes present at odd levels and sum of all nodes present at even level.

(1 + 4 + 5 + 6) – (2 + 3 + 7 + 8) = -4

The idea is to traverse the tree and pass level of each node in recursion. We also pass a variable to store the required difference. If the level of a node is odd, we increase the difference by node’s value else we decrease the difference by same amount. At the end of recursion, the variable will contain the required difference.

Here’s a C++ program that demonstrates it:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Helper function void findDiff(Node *root, int &diff, int level) { // base case if (root == nullptr) return; // if current level is odd if (level & 1) diff += root->data; // if current level is even else diff -= root->data; // recurse for left subtree and right subtree findDiff(root->left, diff, level + 1); findDiff(root->right, diff, level + 1); } // Function to calculate the difference between sum of all nodes present // at odd levels and sum of all nodes present at even level int findDiff(Node *root) { int diff = 0; findDiff(root, diff, 1); return diff; } |

The time complexity of above solution is O(n) and auxiliary space required by the program is O(h) for call stack where h is the height of the binary tree.

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply