# 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. 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++

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

Exercise:

2. Modify the solution to print diagonal sum for diagonals having positive slope (/).     (1 votes, average: 5.00 out of 5) Loading...

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 🙂 Subscribe
Notify of 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. Guest
Mario R. Rincon

It could be inorder instead of preorder, right?