Find the diagonal sum of given binary tree

Given a binary tree, calculate sum of all nodes for each diagonal having negative slope (\). Assume that the left and right child of a node makes 45 degree angle with the parent.

 

For example, consider below binary tree having three diagonals (marked in red). The sum of diagonals is 10, 15 and 11.

 

diagonal-sum

 


 

This problem can be easily solved with the help of Hashing. The idea is to create an empty map where each key in the map represents a diagonal in the binary tree and its value maintains sum of all nodes present in the diagonal. Then we do a pre-order traversal of the tree and update the map. For each node, we recurse for its left subtree by increasing diagonal by 1 and recurse for right subtree with same diagonal.

C++

Download   Run Complete Code

The time complexity of above solution is O(nlog(n)) and auxiliary space used by the program is O(n).
 

Exercise:
1. Extend the solution to print nodes of every diagonal.
2. Modify the solution to print diagonal sum for diagonals having positive slope (/).
 

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

Notify of
avatar
Sort by:   newest | oldest | most voted
Dibyendu
Dibyendu

Hi,

Time complexity: O(nlogn), as each map operation takes O(logn)

Space complexity: O(h) [even though it’s O(n) at worst case]
as O(h) for call stack + O(no of levels of the tree) for map
= O(h) + O(h) = O(h).

Please let me know if I’m wrong.

wpDiscuz