# Top View of Binary Tree

“Top View of Binary Tree” is one of the foremost algorithmic problem asked in technical interviews of product-based companies. Here, we are given a binary tree and our task is to write a program to print the top view of given binary tree.

Top View of Binary Tree is referred to those nodes of binary tree which can be seen from top of the tree.

The idea here is similar to vertical order traversal of binary tree. We will perform the vertical order traversal and print only those nodes which are first nodes of vertical order line.

The steps required to print top view of Binary Tree are as follows:

1. Create a map which store the vertical order line number and corresponding first/top node value.
2. Create a queue which can accommodate both node and corresponding horizontal distance with root node.
3. Insert the root node into queue and 0 as horizontal distance.
4. Perform following steps until queue is node empty.
• Pop front Element of queue.
• Check if popped horizontal distance already present in the map or not. If not, insert the popped node value into map.
• If left child exists of popped node, insert into queue with horizontal distance as current HD-1.
• If right child exists of popped node, insert into queue with horizontal distance as current HD+1.
5. Print the map data which contains top view.

#### C++ Program to print top view of binary tree is as follows:

```/* C++ Program to print top view of Binary Tree */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
int data;
struct Node *left;
struct Node *right;
Node(int ele)
{
data = ele;
left = NULL;
right = NULL;
}
} Node;

/* Function to print top view of Binary Tree */
void topView(Node *root)
{
/* Base Case */
if(root == NULL)
return;

/*
Create a map which store top view nodes
key: vertical order line
pair: Top node of vertical order line
*/
map<int, int> mp;

/*
Create queue which store both node and corresponding HD
*/
queue<pair<Node*, int>> que;
int hd = 0;

que.push(make_pair(root,hd));

while(!que.empty())
{
/* Pop front Node */
pair<Node *,int> temp = que.front();
que.pop();
Node *temp_node = temp.first;
int currHD = temp.second;

/*
If vertical order line is not present in map,
then insert the node value in the map, as it will the
first node of the verical order line
*/
if(mp.find(currHD) == mp.end())
{
mp[currHD] = temp_node -> data;
}

if(temp_node -> left)
que.push(make_pair(temp_node -> left, currHD - 1));

if(temp_node -> right)
que.push(make_pair(temp_node -> right, currHD + 1));
}

/* Print map, which contain top view nodes */
map<int, int> :: iterator itr;
for(itr = mp.begin(); itr != mp.end(); ++itr)
{
cout << itr -> second << " ";
}
}

int main()
{
/* Creating a Binary tree and inserting some nodes in it */
Node *root = NULL;

root = new Node(1);
root -> left = new Node(2);
root -> right = new Node(3);
root -> left -> left = new Node(4);
root -> left -> right = new Node(5);
root -> right -> left = new Node(6);
root -> right -> right = new Node (7);
root -> left -> right -> left = new Node(8);
root -> right -> left -> right = new Node(9);

/* Calling function to print top view of binary tree*/
cout<<"The top View of Given Binary Tree is:\n";
topView(root);
}

```

OUTPUT:

```The top View of Given Binary Tree is:
4 2 1 3 7```

Related Posts: