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:

/ \
2 3
Output: 2 1 3

Example 2:

/ \
20 30
/ \ / \
40 60 90 100
Output: 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).

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


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

// while the queue has elements
// pair points to the front of the queue
pair<struct Node*,int> current = q.front();
// pop the front element from the queue
// if second element in the current pair is equal to the end element in map
//then the value at that index in the map will store the
//data which is held by first element of the current pair

//if element at left is not NULL
// recursive call
//if element at right is not NULL
// recursive call

//vector to store the answer
// pushing the top view elements from the map in the vector
auto p=m.begin();
return ans;


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



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 😎😁.