In this tutorial, we shall solve how to print bottom view of a binary tree.
Problem statement:
You are given a binary tree; you need to print the bottom view of a binary tree.
Consider the tree:
So the solution would be h d b f i g j
This problem can be solved in 4 steps.
Step 1: Calculate the horizontal distance for every node.
Step 2: Create a hash table, list down all the horizontal distance in ascending order.
Step 3: For each horizontal distance, list down all the nodes with similar height. If 2 nodes have the same value, they should be entered in level order traversal order.
Step 4: Finally select the last node from all the horizontal distance.
//add vertical order traversal code here
So how to calculate horizontal distance at every node?
For root node horizontal distance will be 0.
For left Child:
horizontal_distance = parent_horizontal_distance – 1
For Right Child:
horizontal_distance = parent_horizontal_distance + 1
So let’s calculate horizontal distance for all the nodes.
a = root node = 0
b = parent node value – 1 = 0 – 1 = -1
c = parent node value + 1 = 0 + 1 = 1
d = – 1 – 1 = -2
e = – 1 + 1 = 0
f = 1 – 1 = 0
g = 1 + 1 = 2
h = -2 – 1 = -3
i = 2 – 1 = 1
j = 2 + 1 = 3
It can be showed as below:
Now we shall create a hash map in ascending order as below
Now let’s fill the data:
For -1 there is only 1 value, hence insert h
For -2 there is only 1 value, hence insert d
For -1 there is only 1 value, hence insert b
For 0 there is only 3 value, hence insert according to level order traversal. Hence insert a, e, f.
For 1 there is only 2 value, hence insert c, i in order
For 2 there is only 1 value, hence insert g
For 3 there is only 1 value, hence insert j
So the table will look like below:
Now select the last elements, you will get the bottom view:
i.e h d b f i g j
So how can we achieve this in code?
We can use C++ map() stl.
We can define map as “map<int,vector<int>> Map”.
Where the key will hold the horizontal distance, and the value part i.e vector will hold the node value along with the level of the node.
So what we do is, for every new HD, we insert the node level and node value inside the vector as shown below:
if (myMap.find(h_dist) == myMap.end())
{
myMap[h_dist].push_back(level); // push level in index 0
myMap[h_dist].push_back(root -> data); // push node in index 1
}
Why we take level also?
This we do it because, we can replace the node data for the upcoming nodes if the level is greater for the given HD. This we can do it as below:
if (myMap[h_dist][0] <= level) // check if the level is greater than level that is stored for that particular HD
{
myMap[h_dist][0] = level; // If true, update to latest level
myMap[h_dist][1]= root -> data; // and update the data
}
We do above operation because, we want to store only one value per HD, instead of storing multiple values.
Then we print all the values from all the HD filled.
Solution in C++
#include <iostream> #include <vector> #include <map> using namespace std; // structure to hold binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; void print_bottom_view(Node *root, map<int,vector<int>>& map, int level, int h_dist) { // Base case if (root == NULL) return; // if the node is for the first time for given // horizontal distance, add it if (map.find(h_dist) == map.end()) { map[h_dist].push_back(level); map[h_dist].push_back(root -> data); } else { // else, update the level and node details, //only if the given level is greater than the saved level if (map[h_dist][0] <= level) { map[h_dist][0] = level; map[h_dist][1]= root -> data; } } // Calling the function for the right and left subtrees // with the appropriate parameters. print_bottom_view(root -> left, map, level + 1, h_dist - 1); print_bottom_view(root -> right, map, level + 1, h_dist + 1); } int main() { Node* root = nullptr; /* Binary tree: 16 / \ / \ 10 25 / \ / \ / \ / \ 7 15 18 30 */ root = new Node(16); root->left = new Node(10); root->right = new Node(25); root->left->left = new Node(7); root->left->right = new Node(15); root->right->left = new Node(18); root->right->right = new Node(30); map<int,vector<int>> myMap; print_bottom_view(root, myMap, 1, 0); cout<<"The bottom view is"<< endl; for (auto it = myMap.begin(); it != myMap.end(); ++it) { cout << (it-> second)[1]<< " "; } return 0; }
Output:
The bottom view is 7 10 18 25 30