Find the difference between sum of all nodes present at odd and even levels in a binary tree

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.


For example, consider below binary tree. The required difference is

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

Difference between sum of nodes

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:


Download   Run Complete Code

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.

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

Notify of