- Practice
- Data Structures
- Trees
- Tree : Top View
- Discussions

# Tree : Top View

# Tree : Top View

Faland + 28 comments Maybe it needs to add detail about tree representation, i.e. that at any level left subtree never can overlap right subtree and vice versa. In the beginning I was confused - what is expected in following cases:

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

Expected: 4-2-1-3-7 ? In fact - 4-2-1-3.

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

Expected: 8-4-2-1-3 ? In fact - 4-2-1-3, again.

alex_mistery + 23 comments 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`

gauthamk + 2 comments when top view of the tree is asked, which one is meant among the two?

aminoacid + 1 comment Just as @AlexMistery explained

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

codefornand + 2 comments no only printing of leaves will be added

aravindprasad + 2 comments This problem expects solution as @AlexMistery explained.

But the actual Top view seems to be different though.

johnsonjo4531 + 3 comments 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.

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

yogeshkaushik008 + 0 comments It Does, I have submitted the logic of vertical order traversal.

parmarabhishek_1 + 4 comments This is the actual code for top view of a tree :

typedef pair<int,int> v_h; map <int,v_h> m; // map map <int, v_h> :: iterator itr; //itterator void store_view(node * root,int i,int h) { if(root==NULL) return; itr=m.find(i); if(itr==m.end()) m[i]=make_pair(h,root->data); else { if(itr->second.first > h) m[i]=make_pair(h,root->data); } if(root->left!=NULL) store_view(root->left,i-1,h+1); if(root->right!=NULL) store_view(root->right,i+1,h+1); } void print_map() { for(itr = m.begin(); itr != m.end(); ++itr) cout<<itr->second.second<<" "; } void topView(node * root) { store_view(root,0,0); print_map(); return; }

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

void for_left(node * root) { if(root->left!=NULL) for_left(root->left); cout<<root->data<<" "; } void for_right(node * root) { cout<<root->data<<" "; if(root->right!=NULL) for_right(root->right); } void topView(node * root) { if(root->left!=NULL) for_left(root->left); cout<<root->data<<" "; if(root->right!=NULL) for_right(root->right); }

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

digikar99 + 1 comment 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.

xdavidliu + 0 comments 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.

shashikumargund2 + 0 comments it's not working for all the test cases

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

bennattj + 1 comment 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.

archidsouza18 + 2 comments 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 ?

niranjan_wad + 5 comments same question.. Expected output: 1 2 47 49 50 My output: 47 2 1 49 50

archidsouza18 + 1 comment @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 ?

BarryB + 0 comments 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.

bennattj + 0 comments 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).

15A31A0566 + 0 comments Try using TreeMap so the keys will be in sorted order

Sumitkush677 + 0 comments bro..first print traverse, then print that node. then u get correct order

Sumitkush677 + 0 comments first traverse,the print that node. u get correct order

bennattj + 0 comments 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.

pkenil96 + 0 comments 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!

prnvkrjha + 0 comments No! an entire branch could appear in the top view. not just the leaves.

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

sagar_yadav + 1 comment 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 :)

tanmax + 1 comment how can you push sometrhing from front in a vector

boolean_bro + 0 comments vec.push_front(data);

phattantran123 + 0 comments but if this case1 , the top view not see

trideceth12 + 0 comments "truth". If that's a mathematical truth show your proof.

jvedang + 2 comments 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/

Mayur_Detroja + 0 comments 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.

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

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

s0rav + 0 comments really awesome!!

Aniruddha_ + 0 comments [deleted]thedurphy + 2 comments @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.

victortang_com + 0 comments 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)?

bennattj + 0 comments 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).

fheil0815 + 1 comment 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.

VirajSingh19 + 0 comments agreed :)

jason_goemaat1 + 0 comments 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.

1998rahular + 0 comments nice explanation

danielvillaseca + 1 comment 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 << ' '; } }

mayank___17 + 0 comments Doesnt work

AshimGupta + 1 comment 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 .

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

mirwise001 + 0 comments 1 / \ 2 3 \ 5 / \ 4 6 \ 7 \ 8

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

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

noorulh06 + 0 comments 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.

dewscoder + 1 comment 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

ab_in123 + 0 comments 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).

leaveye + 2 comments 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

kvncaldwll + 0 comments 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.

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

leaveye + 0 comments 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.

mikutkin + 0 comments 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?

tanmayvijay + 0 comments [deleted]tanmayvijay + 0 comments `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?`

yhmin84 + 0 comments 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`

.

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

Gprinziv + 1 comment 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.

trideceth12 + 0 comments That makes sense. "For all nodes, everything down the right branch is to the node's right; Everything down the left branch is to the node's left."

It makes sense if you think of it in the context of a binary search tree, and left and right as less than and greater than.

jason_goemaat1 + 0 comments 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'.

Yongping + 0 comments YES, I'm also confused: what's top view......

aravindprasad + 2 comments Dont agree with this problem being tagged as "Easy".

maximshen + 5 comments 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.rajatbarman + 0 comments It caused confusion because GFG defines top view in a different manner than this question. http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/

Wafflenaut + 0 comments I think solving it is easy, but finding an elegant solution seems difficult. Not even sure how you'd do it without adding additional functions or creating something fairly icky.

hackmeifyoucan + 0 comments I just read your comment and solved it in 60 sec. Thanks very much :)

BansheeGhoul + 4 comments This question is just about printing the outermost left or right nodes .. java code (its a version of what parmarabhishek_1 told https://www.hackerrank.com/challenges/tree-top-view/forum/comments/331313 )

java code

void travLeft(Node root){ if(root.left!= null) { travLeft(root.left);} System.out.printf("%d ",root.data); } void travRight(Node root){ System.out.printf("%d ",root.data); if(root.right!= null){ travRight(root.right);} } void topView(Node root) { if(root.left != null){ travLeft(root.left); } System.out.printf("%d ",root.data); if(root.right != null){ travRight(root.right); } }

h415074476 + 1 comment you are right.

BarryB + 0 comments Actually the problem being tested with the test cases is easy. However if you try to solve the problem as defined in GFC, I'd agree that it's not that easy. I actually spent some time trying to solve what GFC describes, but I couldn't get all the test cases to work. When I debugged some of the test cases, I realized that the test cases were all for the simplified case. I then modified my code to support that, and all test cases passed.

After I got all the test cases to work, I actually looked at the editorial, and found the following.

**Note:**This solution is overly simplified and you will need something more complicated for certain types of imbalanced trees.Basically the actual problem statement was not well defined. Either the test cases should support all types of trees, and the problem could potentially be made a medium problem. Or the note should have been put in the problem statement, instead of the editorial.

mvbelgaonkar + 0 comments [deleted]adityaverma82191 + 0 comments this will only pass the 1st test case. i thougth the same logic and i implemented it in c++.

kyxap + 0 comments Will not pass the 2nd TCs :)

jschopick + 0 comments I did this using helper functions and recursion but I printed the left values before the recursive call so it printed in reverse order. I thought I was just fundamentally wrong but I read this comment and then looked at my code in more detail and I just printed after the recursive call and it worked. Thank you!

tvanloon + 1 comment took me two minutes to solve

edemohankrishna1 + 1 comment can you please send me the code Mr tvanloon.I am basic coder please....:)

iam_ghanshyam + 0 comments Its better(learning-wise) to ask for a problem-solving approach instead of solutions.

jogi9045 + 0 comments 8 4 2 1 3

akashBhayekar + 1 comment 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.

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

pkenil96 + 0 comments 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!

panda_whisperer + 0 comments 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.

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

parmarabhishek_1 + 0 comments [deleted]hammeramr + 0 comments Thank you I didnt want to cheat but this makes the problem much easier.

thedurphy + 0 comments [deleted]EmberQuill + 0 comments 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.

Scipsycho + 0 comments 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); }

armagedescu + 0 comments 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.

jason_goemaat1 + 0 comments 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.Dhaminimohandas + 0 comments 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

weiyanen + 0 comments 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); } } } }

octavianarsene + 0 comments Very important details and see the below alex_mistery's comment!

HHWWHH + 0 comments 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

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

tfccomputation + 1 comment 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); }

Blacku + 0 comments this code is only passing the test case 1

vipulvikram + 1 comment here top view means:==>>

`â†—â†˜ â†— â†˜ â†— â†˜ first print from left straight bottom to root and then straight right downword.`

vipulvikram + 0 comments Enjoy..

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

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

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

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

MinhThai2 + 0 comments 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

deepamgupta + 0 comments 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.

xdavidliu + 3 comments Hackers beware! It appears that there was a major change in this problem (in the underlying test cases and checking, but sadly the problem description is highly ambiguous!) and it is no longer sufficient to print the left and right spines. This also invalidates most of the most upvoted comments and answers in this thread from 2-3 years ago. In my opinion, this problem should be labelled Medium or Hard,

*not*Easy!To pass all test cases, you must keep track of the locations of every note in the entire tree, assuming all edges are of the same length and same angle. Hence, nodes may show up in the top view even if they are not in a spine!

Here's a C++ solution that passes all test cases as of July 2018:

using TopTable=map<int, pair<unsigned,int>>; void compute_table_entries(Node *nd, int xpos, unsigned depth, TopTable &tab){ if(nd){ auto it=tab.find(xpos); if(it!=tab.cend() && depth < it->second.first){ it->second = {depth,nd->data}; }else{ tab.insert({xpos, {depth, nd->data}}); } compute_table_entries(nd->left, xpos-1, depth+1, tab); compute_table_entries(nd->right, xpos+1, depth+1, tab); } } void topView(Node * root) { TopTable tab; compute_table_entries(root,0,0,tab); for(auto entry: tab){ cout << entry.second.second << ' '; } }

tech_boy + 0 comments Looks like you made it through, from the previous comments heard that even editorial solutions isn't passing the test cases #strange.

logbob0401 + 0 comments [deleted]venom1724 + 0 comments **Under 10 lines of code C++ solution**Actually there's no need to keep track of depth or to use another function, here's an example solution:

void topView(Node * root) { queue<pair<int,Node*>> q; q.push(make_pair(0,root)); map<int,Node*> ans; for(auto i=q.front();!q.empty();q.pop(),i=q.front()){ if(!i.second) continue; ans.insert(i); q.push(make_pair(i.first+1,i.second->right)); q.push(make_pair(i.first-1,i.second->left)); } for(auto i:ans) cout<<i.second->data<<" "; }

mithratalluri + 2 comments **Solution Explained**(With code)*Note: testcases have been changed for this problem. Hence, the prev. approach shown in popular comments doesn't work.*I'm implementing the tree node with an extra variable called 'node level'. An example of the new tree looks like this:

Here's my code with suitable comments in Java

//new class to store level of each node along with the node static class QueueNode{ Node node; int level; public QueueNode(Node node, int level){ this.node = node; this.level = level; } } public static void topView(Node root) { //took a queue - similar to BFS approach Queue<QueueNode> queue = new LinkedList<QueueNode>(); //Taking a TreeMap<first, second> //first - stores the level of the node //second - stores the node.data TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>(); //why TreeMap? Because I want the nodes to be sorted from leftmost to rightmost //start (since root, level = 0) queue.add(new QueueNode(root, 0)); while(!queue.isEmpty()){ //remove element from queue QueueNode r = queue.poll(); //if the level of this node has never been reached before -> visible in top view if(!map.containsKey(r.level)){ map.put(r.level, r.node.data); } //add node's descendants //all left child node levels = node.level - 1 //all right child node levels = node.level + 1 if(r.node.left != null){ queue.add(new QueueNode(r.node.left, r.level - 1)); } if(r.node.right != null){ queue.add(new QueueNode(r.node.right, r.level + 1)); } } //since already sorted (cuz TreeMap), print from left to right for (Integer value : map.values()) { System.out.print(value + " "); } }

I've written a blog post about this problem here: Trees: Top View of a Tree

*Please upvote this comment if helpful. Thanks! :)*avramsmart + 0 comments Yep this is true, we now have to worry about all nodes, not just one on the sides. Also you have to sort them by levels. This is my solution in Python.

def topView(root): uniq_lvls = [] q = Queue() q.put((root, 0)) while not q.empty(): temp = q.get() if temp[1] not in (i[1] for i in uniq_lvls): uniq_lvls.append(temp) if temp[0].left: q.put((temp[0].left, temp[1]-1)) if temp[0].right: q.put((temp[0].right, temp[1]+1)) for x in sorted(uniq_lvls, key=lambda e: e[1]): print(x[0].info, end=' ')

I am open to your suggestions of how I can improve speed and particularly memory consumption.

sagargupta007 + 0 comments Nice one..!

sadesh + 9 comments `void top_view(Node root) { if(root != null) { top_view(root.left, true); System.out.print(root.data + " "); top_view(root.right, false); } } void top_view(Node node, boolean goLeft) { if(node != null) { if(goLeft) { top_view(node.left, goLeft); System.out.print(node.data + " "); } else { System.out.print(node.data + " "); top_view(node.right, goLeft); } } }`

naveen_n + 3 comments Will this solution work for the below input?

`3 / \ 5 2 / \ / \ 1 46 7 \ 9 / 10 / 11`

I guess "11" will not be printed in spite of it being visible, as the branch containing 9 will not be traversed?

Gprinziv + 0 comments The 9, 10, and 11 nodes are all to the right of the 1 node. If the 1 node had a left child, 12, it's right child would be 13, not 10. You have to expand the tree horizontally for each additional level the tree.

sasi + 0 comments Your example is not a binary tree. void top_view_dir(node *root, int dir) { if(root != NULL) { if(dir) { top_view_dir(root->left, 1); printf("%d ", root->data); } else { printf("%d ", root->data); top_view_dir(root->right, 0); } } } void top_view(node * root) { if(root == NULL) { return; } else { top_view_dir(root->left, 1); printf("%d ", root->data); top_view_dir(root->right, 0); } }

miron88 + 0 comments Exactly. I am looking for a perfect soluction for this problem.

etayluz + 12 comments C solution using recursion without any additional functions with time complexity of O(N) and 0 space complexity. It's the shortest solution on this forum, but it does alter the tree.

`void top_view(node * root) { if (root->left) { root->left->right = NULL; top_view(root->left); } printf("%d ", root->data); if (root->right) { root->right->left = NULL; top_view(root->right); } }`

sanek23994 + 1 comment Provided solution doesn't work if we don't want to modify our tree, right? IMHO usually if want to print some elements in some container it is always better not to modify this container...

joethomas89 + 10 comments Hope this helps, used a static count variable

void top_view(node * root) {

`static int count=0; if (root->left && count>=0) { count++; top_view(root->left); } printf("%d ", root->data); count--; if (root->right && count<0) { count--; top_view(root->right); }`

}

haotie + 0 comments helps a lot! appreciate it

dsaxena + 1 comment your code is giving me an error for the statement "static in count=0;" error is : illegel start of expression

why it is giving such error???

raghav_rao + 1 comment its because of the typo error i guess

"static int count=0;" is right not "static in count=0;"

irfaan_k97 + 0 comments That and the compiler may require you to initialize the static variable

*count*outside of the method (i.e., before it).

vivekimsit + 0 comments I don't think its valid for the skewed second example here http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/ can you please check?

sheksbear + 2 comments Corresponding Java Solution, Thanks it was easy to understand :).

static int count=0;

void top_view(Node root){

`if(root.left!=null && count>=0){ count++; top_view(root.left); } System.out.print(root.data+ " "); count--; if(root.right!=null && count<0){ count--; top_view(root.right); }`

}

angela_pan1992 + 0 comments no need for the "count--" in the second if statement.

vkrrocky + 0 comments wrong code .... its depand on test case...whatever u r getting its fault of hackerrank test case... to verify my argument use this as test case.. 7 2 1 8 7 9 6 5 //level order bst

u will get output as

**"1 2 8 9"**which is wrong..

gmpgiri + 1 comment Whats the significance of using static int here? Using just int gives out error so whats the difference between static int and int and why we using it in this algo?

RFzahid + 1 comment Static variables are executed only once during the entire lifetime of the program unlike normal variables. In the recursive function if we use a normal variable then counter won't be updated as everytime the function is called that variable is set to 0. So we use static variable here as it will only be executed once irrespective of the no of function calls made. So that counter is incremented by 1 everytime the recursive function is called.

patels_manit + 0 comments thanks

145giakhang + 0 comments I think we don't need to count-- when we check in the right subtree of the root since count is already negative now, so we can skip this statement

if (root->right && count<0) { // count--; top_view(root->right); }

lahmer_sidahmed + 0 comments Thank youu , That helped me a lot ;)

onuremreerol + 0 comments Actually in a real world this code just works for one time in an execution. If this method called more than once in one execution for the next call count will be a minus number because of its static behaviour. And top_view never give the left side of the tree. So this solution just for the hackerrank test.

_silent_ + 0 comments beautiful solution

iam_ghanshyam + 0 comments Nice !

vishal_sati + 0 comments Awesome!!!

prendergast + 1 comment And it produces memory leaks!

ace_dexter + 0 comments To clear memory leaks, you need to traverse once again and keep freeing memory before going to the next node. You can try in your machine with extra function for clearing them.

PulkitGarg419 + 0 comments [deleted]peterkirby + 0 comments [deleted]gonca + 0 comments I really like the simplicity and efficiency of your solutions, bravo.

Herat_Patel + 0 comments Thanks man...!

RavikiranCK + 0 comments almost same solution as joethomas89. Basic idea is first travell along the left side of the tree till the last node by incrementing gh var from the child of root and while returning back decrement till root so that gh value will be one less than the initial value of prog. When gh==0 means left side and root are visited now start visiting only the right side. While travelling right side it will not travell left side as we have put consdition gh>=1 and it will be true only at the begginng while travelling left side from the root.

int gh=1;

void top_view(node * root) { if(root->left!=NULL && gh>=1){ ++gh; top_view(root->left); printf("%d ",root->data); --gh; } else if(gh>=1){ printf("%d ",root->data); --gh; return; }

`if(gh==0) { if(root->right!=NULL){ printf("%d ",root->right->data); top_view(root->right); } else{ return; } }`

}

UtsavCodes + 0 comments Excellent thinking. Making the right node null. I am kicking myself for not thinking of this before.

blackL + 0 comments i think you alter the tree;,my answer:

void top_view(node * root) { node * tmp = NULL; if(root->left){ tmp = root->left->right; root->left->right = NULL; top_view(root->left); root->left->right = tmp; } cout<<root->data<<" "; if(root->right){ tmp = root->right->left; root->right->left = NULL; top_view(root->right); root->right->left = tmp; } return; }

skp1415 + 0 comments i think provided solution will not work if left subtree have a right nodes in such a way that all the nodes go past right subtree or vice versa.

manuel_gustavo + 0 comments That would kill this scenario:

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

Top view of the above binary tree is 2 1 3 6

dennysregalado + 0 comments We can merge these two functions in one using default value for the second argument and define 3 possible values for each funcion call: { 0: original, 1: left , 2: right}.

`void top_view(node * root, int src=0) { i f(root == NULL) return; if(src==0){ top_view(root->left, 1); printf("%d ",root->data); top_view(root->right,2); } if(src==1){ top_view(root->left, 1); printf("%d ",root->data); } if(src==2){ printf("%d ",root->data); top_view(root->right,2); } }`

peterkirby + 5 comments Simple version.

`void top_view(node* root, int order = 0) { if (root == NULL) return; if (order <= 0) top_view(root->left, -1); cout << root->data << " "; if (order >= 0) top_view(root->right, 1); }`

LenaElika + 10 comments I came up with a similar solution in Java :) So far, I like it the most.

void top_view(Node root) { top_view(root, 0); } void top_view(Node root, int side) { if (root != null) { if (side <= 0) { top_view(root.left, -1); } System.out.print(root.data + " "); if (side >= 0) { top_view(root.right, 1); } } }

vuleenguyen_92 + 0 comments Your are very good!! Perfect Solution

entropyjx + 0 comments Wow ... that is such a genius, elegant, fast, space efficient algorithm.

And I was failing in trying to adapt a top-view algorithm with a queue helper.

shashi85 + 0 comments [deleted]shashi85 + 0 comments [deleted]shashi85 + 0 comments [deleted]heisenberg_ab + 0 comments Woah, the simplest and best solution to this problem! I didnt think of this that way...

gonsalespalazio + 0 comments Very clever. :) Thank you.

ambitious_girl + 0 comments What's the logic you used in order to develop it? Thank you!

davidwihl + 2 comments I independently came up with a similar solution for Python:

def topView(root,side=0): if root is None: return 0 if side == 0 or side == -1: topView(root.left,side=-1) print root.data, if side == 0 or side == +1: topView(root.right,side=+1) return

HHWWHH + 0 comments [deleted]jae_duk_seo + 0 comments this solution is amazing and graceful

aalapmaru41 + 0 comments Can someone please explain this code? Thank you

rajatbarman + 0 comments The most clever solution I found here :)

Shivan111 + 1 comment I dont think your solution would work if node 6(sample input) had a child in the left or right. Your solution would just skip 6 altogether and print 7 only.

peterkirby + 1 comment That describes a different problem (or different constraints). The other solutions posted here and the editorial can help clarify what is wanted.

https://www.hackerrank.com/challenges/tree-top-view/editorial

kobold + 0 comments [deleted]

rupav + 0 comments Thanks, theses conditions made my submission correct(and i know why)... i used unordered_map to do the same.

rajesh_kashyap60 + 0 comments oh my god! how did u think ?

vuleenguyen_92 + 0 comments Your solution is very good. Thanks

mequint2000 + 0 comments I solved the problem this way as well - it seems more intuitive. If the problem stated that we couldn't use other functions, things would be different.

anujm4467 + 0 comments amazing bro nice idea

kyxap + 0 comments it works only for 1st TC. Not sure if there changed something

evanadams28 + 7 comments My recursive solution. Like you're standing on the spine of a house roof. Look left, look down, look right.

void top_view(Node root) { left_view(root.left); System.out.print(root.data + " "); right_view(root.right); } void left_view(Node root) { if (root == null) return; left_view(root.left); System.out.print(root.data + " "); } void right_view(Node root) { if (root == null) return; System.out.print(root.data + " "); right_view(root.right); }

carlos_rosario11 + 0 comments [deleted]jittenddra + 0 comments perfect adams very good solution

Ridhuvarshan + 1 comment I don't get it. I did the same logic and got the same output except for the fact that they were not in order. How on earth does 'top view' seem to give any idea in the direction to look first. Anyway I am using your logic(same as mine with different order) guilt free as ambiguity in problem statement is not my fault. Thanks

_yash_agarwal_ + 0 comments Maybe, you called rightview recursively before printing data

rajatshukla + 0 comments wow man ..

umbertodovidio + 0 comments Really nice, I made something similar using a stack. But I think using the recursion stack is much more elegant and beautiful

Shruti165 + 0 comments work well

saifulcseng + 0 comments Your solution will not work for the following tree:

tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.right = new Node(4); tree.root.left.right.right = new Node(5); tree.root.left.right.right.right = new Node(6);

agent009 + 0 comments this was crazy. New people here,

. instead fall for the*don't fall for the top rated comments*comments here. seems that testcases got better, and the tougher definition of top view is needed to get an AC here.*newer*

pulikutti + 2 comments Python has not been enabled for this challenge!

DanHaggard + 1 comment Adding my +1 for the python version.

w0203j + 2 comments +1 for Python3

daponster + 0 comments [deleted]sumith_gannarapu + 0 comments +1 for Python3

juharri3 + 0 comments I'm assuming that the further I go into the Data Structure challenges that I'll eventually be left with only the option of Java.

mandarpathak + 4 comments void top_view(Node root) { Node curr = root; Stack<Node> stack = new Stack<Node>(); while(curr != null) { stack.push(curr); curr = curr.left; } while(!stack.isEmpty()){ Node node = stack.pop(); System.out.print(node.data + " "); } curr = root.right; while(curr != null){ System.out.print(curr.data + " "); curr = curr.right; } }

Mingling94 + 1 comment A stack seems overdoing it in terms of space complexity, it may be less elegant, but more practical to print in place.

mequint2000 + 0 comments Not necessarily - using recursion does the same thing; mandarpathak just decided to use his own stack instead of the system stack.

joseph91 + 1 comment `1 / \ 2 3 \ 4 \ 5 \ 6`

Top view of the above binary tree is 2 1 3 6

How about this sample?

Mingling94 + 1 comment It is not, that example would be 213. Only the topmost left and right nodes of a tree are in the topview.

joseph91 + 2 comments I don't think you are right.

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

http://algorithms.tutorialhorizon.com/print-the-top-view-of-a-binary-tree/

You will understand the definition of the top view of a binary tree.That is an interesting question but not as simple as you think.

Mingling94 + 0 comments Yeah those links are cool and informative, but the problem is designed by a person and put on hackerrank. Look to the top comments :P

metaflow + 0 comments Agree. The fact that testcases does not include such case is just a flaw of testcases. You don't need to be such bad as well. Imagine inteview scenario: if you show solution with assumption not stated in problem that is a red flag.

yask123 + 0 comments [deleted]vinayinusa + 0 comments i have the exact same solution, i think this is better in terms of using stack only for traversing left subtree instead of using recursion for both left and right subtrees.

dansummer94 + 1 comment - I assume one recent update has change the code and answer for python 3.
- The desired output has changed from only the nodes on the 'single-direction-branches' to all the nodes you can see from the top, thus a lot of the posted codes is not valid.
- I'm not sure if I can optimize the while part of my code, and I would prefer a version without recursion in python, but the code below is all I can post at the moment.

def topView(root): # deal with empty tree case if root == None: return # tuple (pos, lvl, node.info) tupleList = [(0,0,root.info)] tupleAppend(tupleList, root.left, 0, 0, 'L') tupleAppend(tupleList, root.right, 0, 0, 'R') # select tuples with lowest lvl for each pos tupleList.sort(key = lambda tup: (tup[0], tup[1])) i = 0 while i < len(tupleList) - 1: while tupleList[i][0] == tupleList[i + 1][0]: tupleList.pop(i + 1) if (i + 1) > len(tupleList) - 1: break i += 1 for _, _, data in tupleList: print(data, end = " ") def tupleAppend(ls, node, pos, lvl, direction): if node: if direction == 'L': pos = pos - 1 elif direction == 'R': pos = pos + 1 lvl = lvl + 1 ls.append((pos, lvl, node.info)) tupleAppend(ls, node.left, pos, lvl, 'L') tupleAppend(ls, node.right, pos, lvl, 'R')

tbhesswebber + 0 comments I'm a JS guy, so handling the trees in Python has been a learning experience. I had

*no*idea that print had additional params, so my solution ended up being rather convoluted, building a list of dictionaries that track`node.info`

and vertical and horizontal offsets, eventually gets sorted, and then gets mapped to an array of strings that is joined and printed. It was nasty. HahaThanks!

IamSarthak + 2 comments I think there is problem with their hidden cases.

Sridhar_CR + 1 comment I too hope there is a bug in this

IamSarthak + 0 comments Yeah people are saying that even editorial solution not working

notesalt + 0 comments yes, they aren't working

Sort 505 Discussions, By:

Please Login in order to post a comment