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

**Output: **2 1 3

**Example 2:**

**Input:**

10

/ \

20 30

/ \ / \

40 60 90 100

**Output: **40 20 10 30 100

**Task:**

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.

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)q.push(make_pair(current.first->right,current.second+1));// recursive call

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

- 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 ☕