In this chapter we shall learn how to print top view of a binary tree.
Problem Statement:
You are given a root node of the tree print the top view of the tree.
For example:
Consider the below tree:
So the top view will be
d b a c g
Let’s see how do we arrive at this solution.
We can solve this problem by applying level order traversal and vertical order traversal.
Now let’s see how these 2 traversal will help us to get the top view of the tree.
The level order traversal of the tree will give the result as below:
a b c d e f g
For the vertical traversal we need to calculate the Horizontal Distance.
For the horizontal distance, of the tree is as below:
Now we shall list according to ascending order of the horizontal distance [HD], it will be as below:
Now if we observe the table with HD value of 0, we have written it as “a, e, f” because all the 3 nodes are in the same HD value.
But why we dint write as “e, a, f” or “f, a, e”? Because, we have applied level order traversal and from that we know that “a” comes first, then “e” then f.
From the table it is clear that we need to take the first nodes at each HD value to arrive at the result.
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 smaller for the given HD. This we can do it as below:
if (myMap[h_dist][0] > level) // check if the level is smaller 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 this operation “myMap[h_dist][0] > level” because, from the top view, only the higher level can be seen, the nodes present at the lower level cannot be seen.
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_top_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 // for top view we take the first element at that HD 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 smaller 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_top_view(root -> left, map, level + 1, h_dist - 1); print_top_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_top_view(root, myMap, 1, 0); cout<<"The top view is"<< endl; for (auto it = myMap.begin(); it != myMap.end(); ++it) { cout << (it-> second)[1]<< " "; } return 0; }
Output:
The top view is 7 10 16 25 30