Problem Statement

Top view of a binary tree is the set of nodes visible when the tree is viewed from the top. Given a binary tree, print the top view of it. The output nodes can be printed in any order.

A node x is there in output if x is the topmost node at its horizontal distance. Horizontal distance of left child of a node x is equal to horizontal distance of x minus 1, and that of right child is horizontal distance of x plus 1.

       1
    /     \\
   2       3
  /  \\    / \\
 4    5  6   7
Top view of the above binary tree is
4 2 1 3 7

        1
      /   \\
    2       3
      \\
        4
          \\
            5
             \\
               6
Top view of the above binary tree is
2 1 3 6

Problem Link

Top View of Binary Tree | Practice | GeeksforGeeks

Code (Using BFS)

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)
    {
        queue <pair<Node*,int>> q;
        q.push({root,0});
        unordered_set<int> s;
        vector<pair<int,int>> temp;
        vector<int> res;
        
        while(!q.empty())
        {
            auto curr = q.front();
            q.pop();
            Node *node = curr.first;
            int val = node->data;
            int ht = curr.second;
            
            if(s.find(ht)==s.end())
            {
                s.insert(ht);
                temp.push_back({ht,val});
            }
            if(node->left)
            q.push({node->left,ht-1});
            
            if(node->right)
            q.push({node->right,ht+1});
            
            
            
        }
        sort(temp.begin(),temp.end());//sorting in increasing order of vertical heights
        
        for(auto p:temp)
        res.push_back(p.second);
        
        return res;
        
        
    }

};