Given a binary tree, perform vertical traversal of it. In vertical traversal, we print nodes of a binary tree in vertical order by assuming that the left and right child of a node makes 45 degree angle with the parent.

2, 7

1, 5

3, 8

6

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 all nodes present at same horizontal distance. Then we do a pre-order traversal of the tree and we update 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. For above binary tree, the final values in the map will be

(horizontal distance -> Nodes)

-1 -> [2, 7]

0 -> [1, 5]

1 -> [3, 8]

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 41 42 43 44 45 46 47 48 49 50 |
// 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 printVertical(Node *node, int dist, auto &map) { // base case: empty tree if (node == nullptr) return; // insert nodes present at current horizontal distance into the map map.insert(make_pair(dist, node->data)); // recurse for left subtree by decreasing horizontal distance by 1 printVertical(node->left, dist - 1, map); // recurse for right subtree by increasing horizontal distance by 1 printVertical(node->right, dist + 1, map); } // Function to print nodes of a given binary tree in vertical order void printVertical(Node *root) { // create an empty map where // key -> relative horizontal distance of the node from root node and // value -> nodes present at same horizontal distance multimap<int, int> map; // we can also use map<int, vector<int>> instead of multimap<int, int> // do pre-order traversal of the tree and fill the map printVertical(root, 0, map); // traverse the map and print vertical nodes int temp = 0; for (auto it = map.begin(); it != map.end(); it++) { if (temp != it->first) { cout << endl; temp = it->first; } cout << it->second << " "; } } |

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

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