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.
Output: 2 1 3
/ \ / \
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.
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.
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
// 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
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
// recursive call
q.push(make_pair(current.first->left,current.second-1));//if element at right is not NULL
// recursive call
}//vector to store the answer
vector<int>ans// pushing the top view elements from the map in the vector
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 ☕