Ambiguity with the Top View of a binary tree

Question

What exactly is the top view of a binary tree?

I find great ambiguity and lack of clarity from the articles I find.

For example, this is what is used to demonstrate the top view on geeksforgeeks:

       1
    /     \
   2       3
  /  \    / \
 4    5  6   7

They go on to say that the top view is 4 2 1 3 7. The problem here is that they leave a lot of speculation on what isn't the top view. Consequently it becomes ambiguous to implement in code.

Stackoverflow examples so far are not any better. Hackerrank's example is even worse.

So I am hoping someone will tell me explicitly what the top view is because I have been trying to find out for 2 days. For instance, what is the top view of this tree:

      1
       \
        14
       /  \
      3    15
     / \
    2   7
       /  \
      4     13
     / \   /
    5   6 10
         /  \
        8    11
         \    \
          9    12

And if I may be bold to ask, why is it important?

Answer 1

Now to understand the definition of top view,the best way is to know how to find the top view of a tree.

Finding the top view is a combination of two traversals namely-> Level Order Traversal and Vertical Traversal(There are other ways too but this one is the most basic).

To visualise this,start drawing vertical lines in the tree,in your second example 6 vertical lines would be drawn covering nodes, 1st -> 2,5 || 2nd -> 1,3,4 || 3rd -> 14,7,6,8 || 4th -> 15,13,10,9 || 5th -> 11 || 6th -> 12. Now traverse the leaders of these vertical lines and this will give the top view of the tree 2->1->14->15->11->12.

Its like your're keeping your eye on the top of the tree and start drawing straight lines,the nodes which the straight lines cut first before touching any other nodes is the top view of the tree.

Like all other questions on hackerrank which helps in strengthening your base concept ,finding top view helps you understand the level order traversal and the vertical traversal concepts in detail.

Answer 2

To answer your question i will ask you to assume a rough sketch to actually understand what the question top view asks for. You might assume you are watching this tree with the root of the binary tree as the peak of a tree from a helicopter from above.

Assume the rank of the root to be 0. You need to traverse the tree in level order. If you go towards left decrease the current rank by 1 and when going right increase the current rank by 1. You will then be able to see that only unique values of every rank comes out as output. The rank is actually the horizontal distance from the root node.

Like in the first example :

             ------- 1 (0) -------
            /                     \
        2 (0-1=-1)               3 (0+1=1)
      /           \             /          \
   4 (-1-1=-2)  5 (-1+1=0)    6 (1-1=0)   7 (1+1=2)

In brackets i have written down the ranks to which i was referring to. So the final output if asked to write from left to right as asked in GeeksForGeeks, you can print the corresponding numbers of each unique ranks sorted according to the ranks.

And i guess it is clear now as to why 5 (rank=0) and 6(rank=0) are not in the final answer. Since when seen from the top of a tree these numbers will be shadowed by 1(rank=0).

map<int,int> mp;

void topView(Node * root) {
    if(!root)
        return;

    mp.insert({0,root->data});

    queue<pair<Node*,int>> q;
    q.push({root,0});
    while(!q.empty()){
        Node *tmp=q.front().first;
        int dis=q.front().second;
        q.pop();

        if(tmp->left){
            q.push({tmp->left,dis-1});

            if(mp.find(dis-1)==mp.end()){
                mp.insert({dis-1,tmp->left->data});
            }
        }

        if(tmp->right){
            q.push({tmp->right,dis+1});

            if(mp.find(dis+1)==mp.end()){
                mp.insert({dis+1,tmp->right->data});
            }
        }
    }

    for(auto i : mp){
        cout<<i.second<<" ";
    }

}

The accepted solution to the above problem. Link : Well explained! Refer for step by step explanation. https://stackoverflow.com/a/31388101/13962659