when top view of the tree is asked, which one is meant among the two?

"truth". If that's a mathematical truth show your proof.

If you add underscores to root, why not to all elements?

                       ______1______
                      |             |
                ______2______       3
               |             |
               4             5______
                                    |
                                    6______
                                           |
                                           7

Isn't the my shown diagram show uniformness according to your design? You just broadened the root, if you broaden the root, you will also have to broaden others equally. So its answer will be 4,2,1,3,7

Reference: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/

Mathematically it's what you define it to be, and the exercise's woding is wide open to interpretation.

really awesome!!

http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/

@alex_mistery, I understand what you are saying, however, in my experience, top-view of a binary tree is determined by the combination of Level-Order-Traversal and Vertical-Order-Traversal, in other words, you determine all the nodes that are in the same Vertical-Order but only choose the node in each Order that first appears in the Level-Order list. So when doing this, you get the following...

Level_Order = [1, 2, 3, 4, 5, 6, 7, 8]

Vertical-Orders are the following (0 is root position, all others are delta from root)

Distance_from_root = -2|-1|0|1|2|3
                      4| 2|1|3|7|8
                       |  |5|6| | 

Since 4, 2, 7, 8 are alone in there set, we don't have to refer to the level order choose. In the 0 and 1 Distances from the root, we have [1,5] and [3,6]. 1 occurs first in Level_order over 5, so we choose 1. 3 occurs first in Level_order over 6, so we choose 3. So after eliminating 5 and 6, going from left-right, we get...

4, 2, 1, 3, 7, 8

This is the algo used in Geeks for Geeks and is widely used in all documentation of top-view I've seen. So, @Faland is correct in this respect. Intuitively, the alternative where someone only see the higher levels in the top-view without compensating for vertical displacement doesn't make any sense. Think about how a pyramid works. If I were to take @alex_mistery's interpretation, I shouldn't be able to see the outerbricks on the base of a pyramid if I was looking down from the top no matter how far away from the center those bricks were.

how the hell is that supposed to be mathematical? mathematically a tree is not even a geometric object. and there certainly is no correct way to draw it.

That's not true, you're changing the tree by making the 6 right of the 5. You need to space out those lower levels so 5->6->7->8 still goes to the left, but the 8 is always right of the 2.

nice explanation

Thanks, checking the level sign i was able to solve this problem

void verticalTraversal(node* head, map<int,int> &levelMap, int level) {
    if(head == NULL)
        return;
    if(levelMap.count(level) == 0)
        levelMap[level] = head->data;
    if(level == 0 || level < 0)
        verticalTraversal(head->left, levelMap, level - 1);
    if(level == 0 || level > 0)
        verticalTraversal(head->right, levelMap, level + 1);
}
void topView(node * root) { 
    if (root == NULL)
        return;
 
    map<int, int> levelMap;
    verticalTraversal(root, levelMap, 0);
    
    for (map<int,int>::iterator it=levelMap.begin(); it!=levelMap.end(); ++it) {
        cout << it->second << ' ';
    }
}

Why have you only considered top root like this, why did'nt you made every root level same as the top one ? @Faland is right and geeksforgeeks also refers the same .

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

the diagrams of the problem should have been drawn like this in order not to create ambiguity.

note that this is no longer true; the problem has been changed to the exact opposite!

According to your explaination, I you are asked to print the bottom view of the tree then it it will print all the elements of the tree because they are all visible from bottom. But I think this will not be right.

I coded according to this definition, but the test cases failed except the first one.

Here is a custom test case that I used 7 10 4 3 5 6 7 11 10 / \ 4 11 / \ 3 5 \ 6 \ 7 According the defninition, the output should be 3 4 10 11, and that is what my program also gives, but when I submit the code, except first test case, all other test cases fails

I am really confused with the top view definition. And do not agree with this explaination.

For case:

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

It expects:

2 1 14 15 12

but not:

1 14 15

In that case, why in test case 2 (input 1 14 3 7 4 5 15 6 13 10 11 2 12 8 9) is the expected output 2 1 14 15 12 and not 1 14 15?

void topView(Node * root) {

    vector<int> vL, vR;
    Node *t = root;

    while(t){

        t = t->left;
        if(t) vL.push_back(t->data);
    }

    t = root;

    while(t){

        vR.push_back(t->data);
        t = t->right;
    }

    for(int i=vL.size()-1; i>=0; i--) cout<<vL[i]<<" ";
    for(int i=0; i<vR.size(); i++) cout<<vR[i]<<" ";

}



    Can anyone explain why this code doesn't work?

You can use negative-position array for the nodes in root-left and positive-position array for the nodes in root-right. Using queue, BFS can be used with sending relative position to root. If abs(position) is larger than length of the corrensponding array (if position >0, positive-pos arr, if position <0, negative-pos arr), append the value to corresponding array. If BFS is done, the result is reversed(negative-pos arr) + value_at_zero + positive-pos arr.

Think of it this way, @marcotuliorr. Imagine if that '3' node had three consecutive children "7 - 8 - 9" (each node is the left child of its parent.) Would that branch cross over the long "4 - 5 - 6" branch and make the top-down view of the tree "9 - 2 - 1 - 3 - 6"? Of course not!

Every node's child must retain the positional properties of its parent, I.E. if 2 is to the left of 1, then 4 and 5 must also be to the left of 1. If 5 is to the left of 1, 6 must be to the left of 1 as well, etc. There's no way a branch not on the leftmost or rightmost path could be visible from the top down.

I think that link is wrong. In a binary tree, once you go left, all descendants of that child are by definition left of that parent. To get an accurate spatial representation you have to expand your tree so that the bottom level will fit if it is full. They say:

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

But all nodes 'left' of the 1 should be drawn to the left of the 1. If the tree's bottom level was full it would have 16 nodes and it should be drawn that way. If you add a node '7' left of '3' using this representation, it would overlap with the '4'.

I actually disagree with your disagree.

"Top view" is simply defined as, "Starting from top node, every node added to the right side of top node is every right side node's right node if any, every node added to the left side of top node is every left side node's left node, if any." I just used a linkedlist to append left and right nodes on both sides from center to two ends.

This problem has been completely misleaded by @Faland, unfortunately. And I don't think I am smarter than many folks here, so I kinda curious why this one caused so many confusion.

took me two minutes to solve

The issue is that the problem is poorly defined. You are correct, but that isn't clear from the problem statement.

your code is just passing first test https://pastebin.com/CmTWX5C1

this code is only passing the test case 1

Enjoy..

I feel like this makes the problem quite a bit harder, I don't think it should still be marked as "easy".