# Top View of a Binary Tree

Given below is a binary tree. The task is to print the top view of a binary tree. The top view of a binary tree is the set of nodes visible when the tree is viewed from the top. For the given below tree.

`Note: Return nodes from leftmost node to rightmost node.`

Example 1:

`Input:      1   /    \  2      3Output: 2 1 3`

Example 2:

`Input:       10    /      \  20        30 /   \    /    \40   60  90    100Output: 40 20 10 30 100`

Complete the function topView() that takes the root node as a parameter and returns a list of nodes visible from the top view from left to right. Print endline after the end of printing the top view.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N).

Constraints:
1 ≤ N ≤ 10^5
1 ≤ Node Data ≤ 10^5

I will use the map, pair, and queue for finding the solution. Let us first understand these.

1. Map

It is a container that stores data in key-value pairs as shown in the diagram above. No two mapped values have the same key values.
Some basic functions are : begin(), end(), clear() etc.

2. Pair

It is a container that consists of 2 data elements or containers.

Syntax is : pair (data_type1, data_type2) Pair_name

CODE :

`vector<int> topView(Node *root) { //map where key and value pair are of int type  map<int,int> m;   // queue of pair  queue<pair<struct Node*,int>> q;//constructs a pair object with its first element set to x i.e. root//and its second element set to y i.e. 0 q.push(make_pair(root,0)); // while the queue has elements while(!q.empty()) { // pair points to the front of the queue  pair<struct Node*,int> current = q.front();// pop the front element from the queue  q.pop();// if second element in the current pair is equal to the end element in map  if(m.find(current.second)==m.end())//then the value at that index in the map will store the //data which is held by first element of the current pair  m[current.second]=current.first->data;//if element at left is not NULL  if(current.first->left)// recursive call  q.push(make_pair(current.first->left,current.second-1));//if element at right is not NULL  if(current.first->right)// recursive call  q.push(make_pair(current.first->right,current.second+1));  }//vector to store the answer  vector<int>ans// pushing the top view elements from the map in the vector  auto p=m.begin(); while(p!=m.end()) { ans.push_back(p->second); p++; } return ans; }`

CODE SNIPPET

Refernce for easy understanding & visulaization :

1. Below is the image to show the visualization of the queue of pairs.
`       Queue of Pairs: (10, 20) (15, 5) (1, 5) (5, 10) (7, 9)`

Hope it helps!!😀Since you enjoyed reading my blog , why not buy me a coffee and supoort my work here!! https://www.buymeacoffee.com/sukanyabharati

--

--