It is just your visual perseption of the tree! The truth is that mathematically it looks like this:

   ______1 ______
  /              \
 2                3
/ \
4  5
    \
     6
      \
       7
        \
         8

I think Faland is right. This link correctly defines tree top view: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/

YES, I'm also confused: what's top view......

Dont agree with this problem being tagged as "Easy".

8 4 2 1 3

This problem dosent consider these much cases, it only want you to print left only list and right only list. which can be simply achieved by going extreme left and extreme right. so yeah second is correct for this problem.

I don't think thats how it is!! According to me the output should rather be : 8 4 2 1 3.. I think all we need is to calculate the horizontal distance of each nodes from the root node and print the node and store them in the queue..then print the first node from the queue for each level of horizontal distance!

Had the same expectation after reading the problem statement. Glad I came here before wasting a bunch of time and getting frustrated.

I agree the problem statement needs more examples.

Thanks. My submission failed but when I looked into why it was pretty clear I only a vague/foggy notion of 'top view'.

Thank you I didnt want to cheat but this makes the problem much easier.

Yeah, some more details would be nice, or perhaps using a tree like the OP's examples as one of the problem examples to demonstrate exactly what is meant by "top view". Or just a definition of "top view". I spent quite a while working on a solution that would track how far left and right of center each node was in order to handle a case like the examples above. Then I checked the discussion and realized the problem was way easier than I'd thought.

yeah but technically in your second example it should be 8-4-2-1-3. I am scratching my head for a very long time , they should really add more explanation

void topView(node * root,int fact=0,int lcomp=1,int rcomp=-1) {
    
    if(root==nullptr)
        return;
    
    cerr<<root->data<<": "<<lcomp<<" ' "<<fact<<" ' "<<rcomp<<endl;
    if((fact>rcomp) || (fact<lcomp)){
        cout<<root->data<<" ";
        if(lcomp>rcomp){
            rcomp++;
            lcomp--;
        }
        else if(fact>rcomp)
            rcomp++;
        else if(fact<lcomp)
            lcomp--;
        
        
        
    }
    topView(root->left,fact-1,lcomp,rcomp);
    topView(root->right,fact+1,lcomp,rcomp);
}

I agree with @Faland. The problem is not well described. So, first I searched the internet for top view problem and solved it. https://www.youtube.com/watch?v=c3SAvcjWb1E In fact a correctly solved problem failed the test case. So, I calculated manually and my solution was correct. It took me lot of time to understand that there is meant something else, after looking in this discussion. So, the problem here is not correctly described. Here is also info about top view: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/ Don't cover you with mathematical description. Look through the window, see a tree. What will be the top view of a tree if you cut a branch? Don't cover you with the fact that you can't provide a mathematical description. An algorithm is already a mathematical description, see youtube link. Any tree that is seen through the windows is all maths.

That is just an artifact of how you draw the tree. By definition, everything left of the 1 is left of the 1. To accurately draw your tree, the 3 needs to be right of the 1 and all nodes in the left branch from the 1 should be displayed left of the 1.

This isn't easy to see in the examples because you have a sparse tree, but if you leave enough rooms for the bottom level to be full, you can see why:

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

If you go on and add 7 left of 6 and 8 left of 7, you add two new levels to the tree, and you'll have to space it out to handle all the other nodes possible at that level. No matter what you do, everything right of the 2 will be right of the 2, and left of the 1, being shaded to the link from 1 to 2.

Since the question mentions it is a binary tree, this possibility is ruled out. chect out this link for the properties of binary trees.

http://cs-study.blogspot.in/2012/11/properties-of-binary-tree.html

Yes, I have the same comfusion. And I write a code below: void topView(Node root) { if(root!=null) { Set s = new HashSet(); LinkedList queue = new LinkedList(); Map map = new HashMap(); queue.offer(root); map.put(root.data, 0); while(!queue.isEmpty()) { Node node = queue.poll(); Integer shadow = map.get(node.data); if(!s.contains(shadow)) { System.out.print(node.data + " "); s.add(shadow); } if(node.left != null) { queue.offer(node.left); map.put(node.left.data, shadow-1); } if(node.right != null) { queue.offer(node.right); map.put(node.right.data, shadow+1); } } } }

Very important details and see the below alex_mistery's comment!

LOL. I solved it for the graphical case first and thought that it was at least medium level problem. Now I see that it's a simpler problem. Thanks @Faland

I am a beginner. If I found this place earlier, I would have not spent hours on this unclarified 'easy' question and doubt myself...... In conclusion, two interpretations on this question: 1. Just like what @thedurphy said, this interpretation of top view aligns with this Youtube video and GFG. And code in Python can be like this (Although it does not pass all tests, it aligns with first interpretation):

def topView(root):
    from collections import defaultdict
    queue=[(root,0)]
    hashtable=defaultdict(lambda:[]) 
    for node,level in queue: #level=x-coordinator
        if node!=None:
            hashtable[level].append(node.data) #hashtable, collect node data with the same level#
            queue.extend([(node.left,level-1),(node.right,level+1)]) #add node in sublevel to queue
    if hashtable !=None:
        for level in xrange(min(hashtable.keys()),max(hashtable.keys())+1):
            print hashtable[level][0], #TOPVIEW
    else:
        return None

2. Another interpretation is provided by @trideceth12, which is aligned with all test cases. Although I doubt this interpretation, I still created the Python code for it:

def topView(root):
    #start with left most leaf
    if root.left:
        printleftside(root.left) #print left side top view, from bottom to top (left to right)
    print root.data, #print root
    if root.right:
        printrightside(root.right) #print right side top view, from top to bottom (left to right)

def printleftside(node):
    if node:
        printleftside(node.left)
    else:
        return
    print node.data,

def printrightside(node):
    if node:
        print node.data,
        printrightside(node.right)
    else:
        return

In the end, WHAT do we use TOPVIEW for in terms of both interpretations?

My solution

void topViewL(node * root) {
    if(!root) return;
    topViewL(root->left);
    printf("%d ",root->data);
}

void topViewR(node * root) {
    if(!root) return;
    printf("%d ",root->data);
    topViewR(root->right);
}

void topView(node * root) {
    topViewL(root);
    topViewR(root->right);
}

here top view means:==>>

        ↗↘
     ↗       ↘
 ↗              ↘

first print from left straight bottom to root and then straight right downword.

The problem has been changed now . New ans for above would be as expected i.e., 4-2-1-3-7

Thanks a lot Faland. People confuse for this representation. I retried this question after 3 years and again forgot.

Yes it should be based on horizontal distance from root node. Refer to https://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/

Thanks for the small examples to visualize. This help alot.

This problem looks like we need to generate horizontal, depth pair for each node, then group them by horizontal coordinate, and just collect the minimum depth from each group.

For problem statement:

1 (0, 0) 2 (1, 1) 5 (2, 2) 6 (3, 3) 3 (1, 3) 4 (2, 4)

1 (0, 0)

2 (1, 1) 3 (1, 3)

5 (2, 2) 4 (2, 4)

6 (3, 3)

solution pass all test cases

If we take the tree as in Faland's comment.

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

The answer for which the compiler successfully runs the test is 4-2-1-3-7

and for

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

output is 8-4-2-1-3 which compiler accepts.

You may refer geeks for geeks for the top view.

Java Solution in O(n)

// where n is the number of nodes in the binary tree
public static void topView(Node root) {
    int MAX = 500;    // Otherwise, MAX=getNodeCount(root);
    int[] top = new int[MAX*2];
    Queue<Object[]> queue = new ArrayDeque<>();
    queue.add(new Object[]{root, MAX});
    while(!queue.isEmpty()) {
        Object[] array = queue.remove();
        Node node = (Node)array[0];
        Integer order = (Integer)array[1];
        if(node == null) continue;

        if(top[order] == 0) top[order] = node.data;
        queue.add(new Object[]{node.left, order-1});
        queue.add(new Object[]{node.right, order+1});
    }

    for(int data: top) if(data != 0) System.out.print(data + " ");
}

Here's the Java code, I used the approach from geekstogeeks. I think the question did not specifiy and clearly define what a top view is. The correct implementation which passes all test cases should be according to this https://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/.

public static void topView(Node root) {
        Dictionary<Node, Integer> dictionary = new Hashtable<>();
        Map<Integer, Node> topResult = new TreeMap<>();
        Queue<Node> nodes = new LinkedList<>();

        if (root != null) {
            topResult.put(0, root);
            dictionary.put(root, 0);
            nodes.add(root);
        }

        while (!nodes.isEmpty()) {
            Node current = nodes.remove();
            int currentOrder = dictionary.get(current);

            if (current.left != null) {
                int value = currentOrder-1;

                if (!topResult.containsKey(value)) {
                    topResult.put(value, current.left);
                }
                dictionary.put(current.left, value);
                nodes.add(current.left);
            }

            if (current.right != null) {
                int value = currentOrder+1;

                if (!topResult.containsKey(value)) {
                    topResult.put(value, current.right);
                }
                dictionary.put(current.right, value);
                nodes.add(current.right);
            }
        }

        for (Node node : topResult.values()) {
            System.out.print(node.data + " ");
        }
    }

You understand ,in this question we are talking about Binary tree?? What kind of explanation have you given here??

nope, the expected answers are 4-2-1-3-7 and 8-4-2-1-3 respectively.

I got an AC with this approach only.

public static void topView(Node root) { class levelNode{ Node node; int level; levelNode(int level, Node node){ this.level = level; this.node = node; } } HashMap topviewmap = new HashMap<>(); Queue q1 = new LinkedList<>(); q1.add(new levelNode(0, root)); while(!q1.isEmpty()){ levelNode temp = q1.poll(); if(!topviewmap.containsKey(temp.level)){ topviewmap.put(temp.level, temp.node); } if(temp.node.left != null){ q1.add(new levelNode(temp.level-1, temp.node.left)); } if(temp.node.right != null){ q1.add(new levelNode(temp.level+1, temp.node.right)); } } for(Map.Entry map : topviewmap.entrySet()){ Node temp = map.getValue(); System.out.print(temp.data+" "); } }> i have writen this code but its not working just passing 1 testcase all suggestions will be appriciated.