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.


Download   Run Complete Code

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


1. Extend the solution to print nodes of every diagonal.

2. Modify the solution to print diagonal sum for diagonals having positive slope (/).

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

newest oldest most voted
Notify of


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

It could be inorder instead of preorder, right?