Given a binary tree, print vertical sum of it. Assume, the left and right child of a node makes 45 degree angle with the parent.

For example, vertical sum is shown in below binary tree

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

Below figure shows horizontal distance and level of each node in above binary tree. The final values in the map will be

(horizontal distance -> vertical sum)

-1 -> 9

0 -> 6

1 -> 11

2 -> 6

**C++ implementation –**

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 39 40 |
// 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 map // Here node has 'dist' horizontal distance from the root of the tree void verticalSum(Node *node, int dist, auto &map) { // base case: empty tree if (node == nullptr) return; // update the map map[dist] += node->data; // recurse for left subtree by decreasing horizontal distance by 1 verticalSum(node->left, dist - 1, map); // recurse for right subtree by increasing horizontal distance by 1 verticalSum(node->right, dist + 1, map); } // Function to print the vertical sum of given binary tree void verticalSum(Node *root) { // create an empty map where // key -> relative horizontal distance of the node from root node and // value -> sum of all nodes present at same horizontal distance map<int, int> map; // do pre-order traversal of the tree and fill the map verticalSum(root, 0, map); // traverse the map and print vertical 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:** Extend the solution to print nodes in vertical order.

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