2 ways to find Top-view of a Binary Tree : easy and explained
Kaybee
27404
CBinary TreeHash TableC++QueueInterview

Method 1: Using Map

here, we store the vertical hight index of the node and check if the index already exists in the map that means we have seen a node above this node in the tree so we dont need this node in the Top view.
else if the vh of the node is not in the map means this vertical level did not had any node so this node is the first node in this vetical level or coloumn so add it to map.
all the nodes in the map are the nodes which are encountered first in the vertical traversal.

class Solution
{
    public:
    //Function to return a list of nodes visible from the top view 
    //from left to right in Binary Tree.
    vector<int> topView(Node *root)
    {
        map<int,int> v;

        vector<int> a;
        if(!root) return a;
        queue<pair<Node*,int>> q;
        q.push({root,0});
 
        while(q.size()){
            Node *t = q.front().first;
            int vh = q.front().second;
            q.pop();
            
			 // if this column index already has a 
		    //node we dont need to change it 
            if(v[vh]==0) v[vh]=t->data;   
			
            if(t->left) q.push({t->left,vh-1});
            if(t->right) q.push({t->right,vh+1});

        }
		
      // all the nodes in the map are the nodes which are 
	  // encountered first in the verical traversal so  gives us the top view of the tree
        
        for(auto x:v) a.push_back(x.second);    
        return a;
 
    }

};

Method 2 : Using Deque

If we can give the root a vertical height index =0 then create a count of the left and rightindexes upto ehich we have seen the nodes then each time:

  • if vertical height is lesser then left index then it is a new node at vertical height index l-1.
  • if vertical height is greater then right index then it is a new node at vertical height index r+1.
    role of deque :
    as we need to keep track of the top view feom the leftmost to the rightmost node so,
  1. if we find a new node at left to be in the top view we insert that node to the front of the queue.
  2. if we find a new node to the right of previous rightmost node then we add this node to rear/back of the queue.
    Hence at last the deque will contain all the top view nodes in order from leftmost to rightmost.
class Solution
{
    public:
    //Function to return a list of nodes visible from the top view 
    //from left to right in Binary Tree.
    vector<int> topView(Node *root)
    {
        deque<int> v;
        vector<int> a;
        if(!root) return a;
        queue<pair<Node*,int>> q; 
        q.push({root,0});    
		
		// root node is always in the top-view so: 
        v.push_back(root->data);    
		
		// intially leftmost and rightmost inndexes = root index = 0
        int l=0;      
        int r=0;
        while(q.size()){
            Node *t = q.front().first;
            int vh = q.front().second;
            q.pop();
            
			// new node has a vertical level greater than rightmost tree level till now so, add it to top-view
            if(vh>r) {
                r=vh;
                v.push_back(t->data);
            }
           // new node has a vertical level lesse than leftmost tree level till now so, add it to top-view
            if(vh<l) {
                l=vh;
                v.push_front(t->data);
            }
			//insert children
            if(t->left) q.push({t->left,vh-1});   
            if(t->right) q.push({t->right,vh+1});

        }
        while(v.size()){
            a.push_back(v.front());
            v.pop_front();
        }
        
        return a;
 
    }

};

Do Upvote if u like!
Happy coding.

Comments (3)