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 Binary Tree
 

 

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 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Dibyendu
Guest
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.

Mario R. Rincon
Guest
Mario R. Rincon

It could be inorder instead of preorder, right?