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

For example, Bottom view of below tree is 7, 5, 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 the node from the root node and value in the map maintains a pair containing node’s value and its level number. Then we do a pre-order traversal of the tree and if current level of a node is more than or equal to maximum level seen so far for the same horizontal distance as current node’s or current horizontal distance is seen for the first time, we update the value and the level for current horizontal distance in the map. For each node, we recurse for its left subtree by decreasing horizontal distance and increasing level by 1 and recurse for right subtree by increasing both level and 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 -> (node’s value, node’s level))

-1 -> (7, 4)

0 -> (5, 3)

1 -> (8, 4)

2 -> (6, 3)

## 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 39 40 41 42 43 44 45 46 47 48 49 |
// Data structure to store a Binary Tree node struct Node { int key; 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 and level represent level of the node void printBottom(Node *node, int dist, int level, auto &map) { // base case: empty tree if (node == nullptr) return; // if current level is more than or equal to maximum level seen so far // for the same horizontal distance or horizontal distance is seen for // the first time, update the map if (map.find(dist) == map.end() || level >= map[dist].second) { // update value and level for current distance map[dist] = { node->key, level }; } // recurse for left subtree by decreasing horizontal distance and // increasing level by 1 printBottom(node->left, dist - 1, level + 1, map); // recurse for right subtree by increasing both level and // horizontal distance by 1 printBottom(node->right, dist + 1, level + 1, map); } // Function to print the bottom view of given binary tree void printBottom(Node *root) { // create an empty map where // key -> relative horizontal distance of the node from root node and // value -> pair containing node's value and its level map<int, pair<int, int>> map; // do pre-order traversal of the tree and fill the map printBottom(root, 0, 0, map); // traverse the map and print bottom view for (auto it: map) cout << it.second.first << " "; } |

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

**Exercise:** Modify the solution to print top view of binary tree

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

Why the usage of Map causes the time complexity to be

O(nlogn)?Thanks for sharing your concerns. Since keys in

std::mapare returned in sorted order, the solution would print the nodes in the desired order from left to right.Alternately, we can use

std::unordered_mapand maintain two variables for storing the min and max horizontal distance. Then we loop from min to max horizontal distance, and print the values present in unordered map corresponding to the horizontal distance.As you use map it’s O(nlogn)

Thanks for bringing this up. We have updated the complexity.