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.

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Recursive function to do a pre-order traversal of the tree and // fill the map with diagonal sum of elements void diagonalSum(Node* root, int diagonal, auto &map) { // base case: empty tree if (root == nullptr) return; // update the current diagonal with node's value map[diagonal] += root->data; // recurse for left subtree by increasing diagonal by 1 diagonalSum(root->left, diagonal + 1, map); // recurse for right subtree with same diagonal diagonalSum(root->right, diagonal, map); } // Function to print the diagonal sum of given binary tree void diagonalSum(Node* root) { // create an empty map to store diagonal sum for every slope map<int, int> map; // do pre-order traversal of the tree and fill the map diagonalSum(root, 0, map); // traverse the map and print diagonal sum for (auto it: map) cout << it.second << " "; } |

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

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.

Dibyendu, thanks for your inputs.

You’re right about Space complexity for call stack but map might not require space equal to no of levels of the tree. For example, consider a skewed tree having slope. It would contain only one map entry but has height of n. Consider another skewed tree having / slope. In this case, map contains n entries.

Hi,

Thanks for your reply. Yes you are right about skewed tree cases which are two extreme cases where h = n. But O(h) still holds true here. But in all other cases O(h) is more asymptotically tighter than O(n).