# 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:

- Create a map which store the vertical order line number and corresponding first/top node value.
- Create a queue which can accommodate both node and corresponding horizontal distance with root node.
- Insert the root node into queue and 0 as horizontal distance.
- 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.

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

**Bottom View of Binary Tree****Delete Complete Binary Tree****Check if two trees are mirror Trees of Each Other****Convert Binary Tree to its Mirror Tree****Check if Binary Tree is Symmetric or Not****Print All Root to Leaf Paths in a Binary Tree****Introduction to Tree Data Structure****Binary Tree Traversals****Print All Leaf Nodes of a Binary Tree****Count Number of Nodes in a Binary Tree****Print Alternate Levels of Binary Tree****Maximum Width of Binary Tree****Level Order Tree Traversal****Left View of Binary Tree****Right View of Binary Tree****Compute Height of Binary Tree****Inorder Tree Traversal Using Stack****Preorder Tree Trasversal Using Stack****Postorder Tree Traversal Using Stack****Vertical Order Tree Traversal**