Nerd For Tech
Published in

Nerd For Tech

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.

  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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sukanya Bharati

Sukanya Bharati

A happy , motivated & a curious soul if you end up finding me 😎😁.