We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

When I visited this question there was no definition for top view given so I had to search for a definition. I came to the geeks for geeks link that others have referenced and made my algorithm according to geeks for geeks' definition which is the same as @Faland's and it was still accepted no problem. There was also only two test cases when I submitted. I honestly think you can submit either way and be fine unless my submission is not implementing geek for geek's definition of top view correctly.

You are spot onn in identifying two different implementations .. looks like this question demands just the outer values of the tree. Thanks once again.

Isn't it the second solution that is expected - the first solution passes in July '18! Seems like they changed the meaning; and if so, I don't think this is a "easy" problem - a "medium" one.

it seems the second part of parmarabhishek_1's post was what the problem originally expected, and that was incorrect. They changed it to correctly require the solution in the first part, as you pointed out. They should have also used a better example to illustrate this subtle point.

Yep, the definition of "Top-View" was never presented in this problem. Besides the grammatical errors in the sentence "explaining" top-view, it almost literally says: when you view from the top, you'll see the top view.

The definition I found, that made sense was from the geeks for geeks link. So I solved it that way. I failed everything past the first test. So I looked at the input/output for the second test case.

For anyone interested, it's clear that the input is given as a binary search tree. So I constructed the graph from the input, ran my program, got the correct result but with extras (to the right for the second test case).

Then figured I was getting extras because a subtree was "poking" out and they didn't want that. So deleted all of my (more complicated) code for what amounted to a trivial problem.

If you hover of the submission results that failed, there will be a popup that appears, where you can download both the input and expected output for that test case.

You appear to have the correct output, but in the wrong order. The solution wants it "left-to-right" (which just so happens to be least-to-greatest since these are apparently
binary search trees).

The root is 47 (the first node given), the rest are input as a binary search tree, which means 2 is the left child of 47. 40 is the right child of 2 (because it's less than 47 but greater than 2), 20 is the left child of 40 (less than 47, greater than 2, and less than 40)...etc.

The input given in the question is in Binary search Insertion type. Like 47 is root node , 2 is smaller than 47 therefore ,on the left side of 47. 40 is smaller than 47 and greater than 2 , therfore 40 is the right child of 2, similarly in this way tree is constructed.

Exactly!!
Even i got that the other way..
I coded the solution considering the horizontal distances of the nodes and all my test cases(except the sample case) failed!
The actual top view certainly is different than what they expects!

no , by the way it become more easy that way u just have to traverse left and store all in vector(push tis data from front) then just traverse right and store it in same vector(push this data from back) then simply print the data or u can use recurssion :)

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

if you only have same space everywhere how can you add left child of 3, so really parents have twice width of branch then children so all the nodes can be set.

@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)

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.

I watched a video on Youtube giving the same explanation as you did. However, what confused me is why level order traversal should be referred? Why can't we print the first node for each horizontal distance stored in the Vertical Order traversal dictionary (which is the top node of each HD)?

FYI, there is a problem with this definition. You can have overlap of the "top" nodes. For instance, when looking "to the left", you could have a branch "poke" out that coincides with another branch. In this case both nodes would appear to be at both the same level and height. My assumption (in my solution) for a tie was the the "left-most" branch was the highest--that is the branch that originated from the "most" left position (in this case that would be how I drew it).

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.

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 .

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

Yeah, the pattern in which they want the output is different from the geeksforgeeks order. The val that is considered there is the horizontal distance, so, here I guess they want the vertical order with the least value of horizontal distance (i.e. the farthest left first).

Yeah, this is the straightforward definition of top view, and at the beginning I think so too. but some test case, and the above explanation break that.

I was left for months, so this situation may changed now.

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.

The idea is that for each node traversed, if that node has a horizontal distance(distance from the centre of the tree) which no other node has had so far, map that horizontal distance to the value of that node.

It goes down the tree and stores the first nodes which are at all the possible distances from the root

## Tree : Top View

You are viewing a single comment's thread. Return to all comments →

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

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

Just as @AlexMistery explained

If the other was true, it would be much tougher to code. Isn't that?

no only printing of leaves will be added

This problem expects solution as @AlexMistery explained.

But the actual Top view seems to be different though.

When I visited this question there was no definition for top view given so I had to search for a definition. I came to the geeks for geeks link that others have referenced and made my algorithm according to geeks for geeks' definition which is the same as @Faland's and it was still accepted no problem. There was also only two test cases when I submitted. I honestly think you can submit either way and be fine unless my submission is not implementing geek for geek's definition of top view correctly.

If we follow algo given by geeksforgeeks then it doesnt give right answer. Geeks for geeks alfo print according @Faland

It Does, I have submitted the logic of vertical order traversal.

This is the actual code for top view of a tree :

but the problem demands the top view according to the root node only :

You are spot onn in identifying two different implementations .. looks like this question demands just the outer values of the tree. Thanks once again.

Isn't it the second solution that is expected - the first solution passes in July '18! Seems like they changed the meaning; and if so, I don't think this is a "easy" problem - a "medium" one.

it seems the second part of parmarabhishek_1's post was what the problem originally expected, and that was incorrect. They changed it to correctly require the solution in the first part, as you pointed out. They should have also used a better example to illustrate this subtle point.

it's not working for all the test cases

I think you are printing root->data 3 times in the topView() function.

no he cancelled out repetitions by using root->left and root->right as initializers in the two functions

Yep, the definition of "Top-View" was never presented in this problem. Besides the grammatical errors in the sentence "explaining" top-view, it almost literally says: when you view from the top, you'll see the top view.

The definition I found, that made sense was from the geeks for geeks link. So I solved it that way. I failed everything past the first test. So I looked at the input/output for the second test case.

For anyone interested, it's clear that the input is given as a binary search tree. So I constructed the graph from the input, ran my program, got the correct result but with extras (to the right for the second test case).

Then figured I was getting extras because a subtree was "poking" out and they didn't want that. So deleted all of my (more complicated) code for what amounted to a trivial problem.

can anyone explain how to represent the tree for this input, 47 2 40 20 38 30 14 28 10 16 19 44 39 27 7 9 31 12 43 21 5 41 34 49 13 33 3 4 25 22 29 15 32 35 6 24 23 26 1 11 42 36 37 17 18 8 45 48 50 46 ? what is root of this tree ?

same question.. Expected output: 1 2 47 49 50 My output: 47 2 1 49 50

@niranjan_wad how did you manage to find the output? Since, it does not tell what is your output. do you know what is root of above question ?

If you hover of the submission results that failed, there will be a popup that appears, where you can download both the input and expected output for that test case.

You appear to have the correct output, but in the wrong order. The solution wants it "left-to-right" (which just so happens to be least-to-greatest since these are apparently binary search trees).

Try using TreeMap so the keys will be in sorted order

bro..first print traverse, then print that node. then u get correct order

first traverse,the print that node. u get correct order

The root is 47 (the first node given), the rest are input as a binary search tree, which means 2 is the left child of 47. 40 is the right child of 2 (because it's less than 47 but greater than 2), 20 is the left child of 40 (less than 47, greater than 2, and less than 40)...etc.

The input given in the question is in Binary search Insertion type. Like 47 is root node , 2 is smaller than 47 therefore ,on the left side of 47. 40 is smaller than 47 and greater than 2 , therfore 40 is the right child of 2, similarly in this way tree is constructed.

Exactly!! Even i got that the other way.. I coded the solution considering the horizontal distances of the nodes and all my test cases(except the sample case) failed! The actual top view certainly is different than what they expects!

No! an entire branch could appear in the top view. not just the leaves.

Not much tough though. I wrote the code with that assumption only. Problem writers need to do a better job here.

no , by the way it become more easy that way u just have to traverse left and store all in vector(push tis data from front) then just traverse right and store it in same vector(push this data from back) then simply print the data or u can use recurssion :)

how can you push sometrhing from front in a vector

vec.push_front(data);

but if this case1 , the top view not see

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

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

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/

if you only have same space everywhere how can you add left child of 3, so really parents have twice width of branch then children so all the nodes can be set.

i have the same question .This case will definitely leads to failure of our logic

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...

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

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...

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.

I watched a video on Youtube giving the same explanation as you did. However, what confused me is why level order traversal should be referred? Why can't we print the first node for each horizontal distance stored in the Vertical Order traversal dictionary (which is the top node of each HD)?

FYI, there is a problem with this definition. You can have overlap of the "top" nodes. For instance, when looking "to the left", you could have a branch "poke" out that coincides with another branch. In this case both nodes would appear to be at both the same level and height. My assumption (in my solution) for a tie was the the "left-most" branch was the highest--that is the branch that originated from the "most" left position (in this case that would be how I drew it).

Now, that's some Editorial-grade insight take notes, lads!

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.

agreed :)

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

Doesnt work

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 .

we should have level orders from top(root). So according to this question, we can only consider for root alone.

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.

Yeah, the pattern in which they want the output is different from the geeksforgeeks order. The val that is considered there is the horizontal distance, so, here I guess they want the vertical order with the least value of horizontal distance (i.e. the farthest left first).

I am really confused with the

`top view`

definition. And do not agree with this explaination.For case:

It expects:

but not:

exact same issue I am having.

from what I understand, the top view outputs should be in ascending order. but the expected answers from the tests seem to break this rule.

you may check this https://www.youtube.com/watch?v=c3SAvcjWb1E

Yeah, this is the

`straightforward`

definition of`top view`

, and at the beginning I think so too. but some test case, and the above explanation break that.I was left for months, so this situation may changed now.

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?

I think you have the same problem as me with what they mean by top-view but I'd like to point out some tiny improvements to your code.

Storing outputs in a vector is a pointless inefficiency. You can cout in your loops instead of pushing the values to a vector that prints after.

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`

.C++ solution :

eplain hd[root->data]=root->data; if (!m[hd[root->left]]) m[hd[root->left]] = root->left->data;

The idea is that for each node traversed, if that node has a horizontal distance(distance from the centre of the tree) which no other node has had so far, map that horizontal distance to the value of that node.

It goes down the tree and stores the first nodes which are at all the possible distances from the root

Can't we say print all left most and right most elements of root node ?