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.

 
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

avatar
  Subscribe  
Notify of