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?

Histology

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.

Metheglin

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://mcmap.net/q/871804/-trying-to-print-top-view-of-a-tree-using-two-if-statements

Innoxious

Answer 3

I don't know of a technical or mathematical definition for you, but it would appear from the links that the top view of the tree is as follows:

Imagine your tree laid out on the surface of a table. Look from the root end of the table down along the length of it. Supposing that the values of nodes are written on small wooden blocks, and the links between them are represented by wooden blocks high enough to obscure any nodes behind them, which nodes can you see when you lower your head to table height? In the first example, 5 and 6 are obscure, whereas 2, 3, 4 and 7 extend outwards to the left or right such that they are still visible.

However, as your second example illustrates, this is ambiguous as to whether or not the nodes 2, 5, 11, 12, 13 extend far enough outwards to be visible.

It seems like a poorly defined concept, which probably means it's not worth worrying about.

Peterus

Answer 4

I noticed that nobody explains why you need to use level order traversal exactly and not simply any other kind of recursive traversals.

And here's the reason: a binary tree might have skewed left subtree by overlapping the right one beneath it or vice versa, take a look at the examples below.

A                     B
      1                  5
     / \                / \
    4   2              4   7
     \   \            /   /
      6   5          9   11
       \                /   
        3              13
         \            /
          11         7
           \        /
            2      3

So if you traverse left nodes first you will have wrongly written right first w:node values in test case A and if you start traversing right nodes first then testcase B fails

Only traversing level by level guarantees that you store a correct top view values.

Turman

Answer 5

It works well and easy solution

import java.util.*;
import java.io.*;
class Node {
    Node left;
    Node right;
    int data;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class Solution {

    /*

    class Node
        int data;
        Node left;
        Node right;
    */
    class Nodegen
    {
        Node node;
        int gen;
        public Nodegen(Node node,int gen)
        {
            this.node=node;
            this.gen=gen;
        }
    }
    public static void topView(Node root) {
        Map<Integer,Nodegen> topview=new TreeMap<>();
        new Solution().printView(root,0,0,topview);
        //  System.out.print(topview.size());
        for (Map.Entry<Integer, Nodegen> entry : topview.entrySet()) {
            System.out.print(entry.getValue().node.data+" ");
        }


    }

    public  void printView(Node root,int align,int gen,Map<Integer,Nodegen> map) {
        if(root==null)
        {
            return ;
        }
        if(map.get(align)==null)
        {
            map.put(align,new Nodegen(root,gen));
        }else{
            if(map.get(align).gen>gen)
            {
                map.put(align, new Nodegen(root,gen));
            }
        }
        int temp=align+1;
        int temp1=align-1;
        int temp2=gen+1;
        printView(root.left,temp1,temp2,map);
        printView(root.right,temp,temp2,map);
    }

    public static Node insert(Node root, int data) {
        if(root == null) {
            return new Node(data);
        } else {
            Node cur;
            if(data <= root.data) {
                cur = insert(root.left, data);
                root.left = cur;
            } else {
                cur = insert(root.right, data);
                root.right = cur;
            }
            return root;
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        Node root = null;
        while(t-- > 0) {
            int data = scan.nextInt();
            root = insert(root, data);
        }
        scan.close();
        topView(root);
    }
}

Crespo

Answer 6

The ancient Chinese sages said that one beget two, two beget three, and three beget all things. Any complex system is made up of the connection of simple parts. The connection must have two connected things, namely the left side and the right side. At the same time, the "connection" itself can be regarded as one thing, the left side, the right side and the connection. Three types of things can form any complex system. Of course, we can further specify the characteristics or rules of things placed on the left and right sides, and we can also specify the relationship or rules between each side and the connection. I think binary trees fit right in with this simple philosophy.this is why binary trees are so important!

Marla