5.Tree : Top View

Top view means when you look the tree from the top the nodes, what you will see will be called the top view of the tree.

       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

Solution:

This solution is based on level order traversal and vertical order traversal using maps.

void topView(Node *root)
{

    int newHd;
    Node *p = NULL;
    map<int, int> m;
    queue<Node *> q;
    queue<int> hd;
    q.push(root);
    hd.push(0);

    while (!q.empty())
    {
        p = q.front();
        q.pop();

        int x = hd.front();
        hd.pop();

        if (m.find(x) == m.end())
        {
            m.insert({x, p->data});
        }
        
        if (p->left)
        {
            newHd = x - 1;
            q.push(p->left);
            hd.push(newHd);
        }

        if (p->right)
        {
            newHd = x + 1;
            q.push(p->right);
            hd.push(newHd);
        }
    }

    for (auto itr = m.begin(); itr != m.end(); itr++)
    {
        cout << itr->second << " ";
    }

Time Complexity:- O(n log(n) )