Faland 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 \ 7Expected: 4-2-1-3-7 ? In fact - 4-2-1-3.
1 / \ 2 3 / \ 4 5 / 6 / 7 / 8Expected: 8-4-2-1-3 ? In fact - 4-2-1-3, again.
alex_mistery 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 when top view of the tree is asked, which one is meant among the two?
aminoacid Just as @AlexMistery explained
amazinghacker If the other was true, it would be much tougher to code. Isn't that?
codefornand no only printing of leaves will be added
aravindprasad This problem expects solution as @AlexMistery explained.
But the actual Top view seems to be different though.
johnsonjo4531 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 If we follow algo given by geeksforgeeks then it doesnt give right answer. Geeks for geeks alfo print according @Faland
yogeshkaushik008 It Does, I have submitted the logic of vertical order traversal.
parmarabhishek_1 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 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 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 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 it's not working for all the test cases
lishantsahu I think you are printing root->data 3 times in the topView() function.
sushils no he cancelled out repetitions by using root->left and root->right as initializers in the two functions
bennattj 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 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 same question.. Expected output: 1 2 47 49 50 My output: 47 2 1 49 50
archidsouza18 @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 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 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 Try using TreeMap so the keys will be in sorted order
Sumitkush677 bro..first print traverse, then print that node. then u get correct order
Sumitkush677 first traverse,the print that node. u get correct order
bennattj 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 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 No! an entire branch could appear in the top view. not just the leaves.
euler Not much tough though. I wrote the code with that assumption only. Problem writers need to do a better job here.
sagar_yadav 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 how can you push sometrhing from front in a vector
boolean_bro vec.push_front(data);
phattantran123 but if this case1 , the top view not see
trideceth12 "truth". If that's a mathematical truth show your proof.
jvedang If you add underscores to root, why not to all elements?
______1______ | | ______2______ 3 | | 4 5______ | 6______ | 7Isn'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 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 i have the same question .This case will definitely leads to failure of our logic
Litecoin Mathematically it's what you define it to be, and the exercise's woding is wide open to interpretation.
s0rav really awesome!!
Aniruddha_ [deleted]thedurphy @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 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 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).
mlvl_jr Now, that's some Editorial-grade insight take notes, lads!
fheil0815 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 agreed :)
jason_goemaat1 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 nice explanation
danielvillaseca 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 Doesnt work
ismailashish786 [deleted]
AshimGupta 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 we should have level orders from top(root). So according to this question, we can only consider for root alone.
mirwise001 1 / \ 2 3 \ 5 / \ 4 6 \ 7 \ 8
xdavidliu the diagrams of the problem should have been drawn like this in order not to create ambiguity.
xdavidliu note that this is no longer true; the problem has been changed to the exact opposite!
noorulh06 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 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 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 I am really confused with the
top viewdefinition. 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 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 you may check this https://www.youtube.com/watch?v=c3SAvcjWb1E
leaveye Yeah, this is the
straightforwarddefinition oftop 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 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 [deleted]tanmayvijay 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?josh_greig 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.
yhmin84 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.sarathy_v_krish1 C++ solution :
void topView(Node* root) { if (!root) return; map<Node*, int> hd; map<int, int> m; deque<Node*> q; q.push_back(root); hd[root]=0; m[hd[root]]=root->data; while(!q.empty()) { if (root->left) { hd[root->left] = hd[root]-1; if (!m[hd[root->left]]) m[hd[root->left]] = root->left->data; q.push_back(root->left); } if (root->right) { hd[root->right] = hd[root]+1; if (!m[hd[root->right]]) m[hd[root->right]] = root->right->data; q.push_back(root->right); } q.pop_front(); if (q.size()) root = q.front(); } map<int, int>::iterator it = m.begin(); while(it!=m.end()) { cout << it->second << " "; it++; } }
saketbharti20171 eplain hd[root->data]=root->data; if (!m[hd[root->left]]) m[hd[root->left]] = root->left->data;
sarathy_v_krish1 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
pandeysdr16 Can't we say print all left most and right most elements of root node ?
marcotuliorr I think Faland is right. This link correctly defines tree top view: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/
Gprinziv 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 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 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 YES, I'm also confused: what's top view......
aravindprasad Dont agree with this problem being tagged as "Easy".
maximshen 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 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 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 I just read your comment and solved it in 60 sec. Thanks very much :)
BansheeGhoul 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 you are right.
BarryB 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 [deleted]adityaverma82191 this will only pass the 1st test case. i thougth the same logic and i implemented it in c++.
kyxap Will not pass the 2nd TCs :)
ioluwayo This only passes the sample and first test case
jschopick 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 took me two minutes to solve
edemohankrishna1 can you please send me the code Mr tvanloon.I am basic coder please....:)
iam_ghanshyam Its better(learning-wise) to ask for a problem-solving approach instead of solutions.
jogi9045 8 4 2 1 3
akashBhayekar 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 The issue is that the problem is poorly defined. You are correct, but that isn't clear from the problem statement.
pkenil96 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 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 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 [deleted]
hammeramr Thank you I didnt want to cheat but this makes the problem much easier.
thedurphy [deleted]
EmberQuill 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 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 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 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 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 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 Very important details and see the below alex_mistery's comment!
HHWWHH 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?
nirajkamdar27 [deleted]nirajkamdar27 your code is just passing first test https://pastebin.com/CmTWX5C1
tfccomputation 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 this code is only passing the test case 1
vipulvikram here top view means:==>>
↗↘ ↗ ↘ ↗ ↘ first print from left straight bottom to root and then straight right downword.vipulvikram Enjoy..
TarunSikka The problem has been changed now . New ans for above would be as expected i.e., 4-2-1-3-7
sam_littlefair I feel like this makes the problem quite a bit harder, I don't think it should still be marked as "easy".
rishabhagarwal19 Thanks a lot Faland. People confuse for this representation. I retried this question after 3 years and again forgot.
hisaravanankesa1 Yes it should be based on horizontal distance from root node. Refer to https://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/
MinhThai2 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 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.
tat_lim 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 + " "); }imjunqing 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 + " "); } }
pranav_gautam82 You understand ,in this question we are talking about Binary tree?? What kind of explanation have you given here??
xdavidliu 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 Looks like you made it through, from the previous comments heard that even editorial solutions isn't passing the test cases #strange.
logbob0401 [deleted]
venom1724 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<<" "; }
dcodeforyou [deleted]
mittal01091997 This is the most brilliant solution of this problem.
mithratalluri 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 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.
gelmilorenzo Hi, this seemed quite faster in a couple benchmark I ran. The main difference is the usage of dictionaries (that probably can check for items faster than in your code, to check for existence) and the queue removal. Also, the "node, score" assignation avoid some indexing I believe...
def topView(root): # Initialize the level this_level = [(root, 0)] scores = {} while this_level: # Basically iterate over the nodes on a single level for _ in range(len(this_level)): node, score = this_level.pop(0) # Skip empty nodes if not node: continue # Store the score if it's a new one! if score not in scores: scores[score] = node.info # Add the node children to the next level this_level.extend( [(node.left, score - 1), (node.right, score + 1)]) # Sort the scores and print their values # (By default the sort is on the tuple first element: the score) for _, value in sorted(list(scores.items())): print(value, end=' ')
Good coding.
renato314159 Trying to decipher some of your logic (thanks for the comments, they're a huge help).
what is happening in this line?
for _ in range(len(this_level)): node, score = this_level.pop(0)Thanks
gelmilorenzo Each time the while begins, I expects all and only the nodes of a single level to be in this_level.
for _ in range(len(this_level)):
This line allows me to iterates only on the nodes in a single level, as their amount is the initial length. If _ confuses you, it's just a convention symbol that states you don't need and won't use the corresponding variable, in this case the loop index.
node, score = this_level.pop(0)
The pop function removes the first element of the list. I remove the first since I am going to extend the list with the next level. As the element I am going to pop is a tuple, I can assign both variable on a single line, thanks to Python sintax.
Feel free to keep asking! :)
renato314159 okay, i finally understand it.
Thank you so much!
renato314159 wait no, sorry, one last thing.
this_level.extend()why use extend instead of append?
I used a similar solution with the level order traversal one but used append instead.
gelmilorenzo Extend is more suitable (and faster) when you need to "append" more than one thing at a time (any iterable). Since I need to add two items (left and right), it is preferable.
N.B.: I could also have used a simple "+=" (which is infinitesimally faster), but this is more explicit and I prefer it for such things.
sagargupta007 Nice one..!
yudhaaditamaput1 Hi, Would you mind to explain your code? I am confused what is the purpose of using 2 different data structure LinkedList and TreeMap?and why it should remove the queueNode r but you still use the r.level and r.node.data?
sadesh 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 Will this solution work for the below input?
3 / \ 5 2 / \ / \ 1 46 7 \ 9 / 10 / 11I guess "11" will not be printed in spite of it being visible, as the branch containing 9 will not be traversed?
Gprinziv 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 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 Exactly. I am looking for a perfect soluction for this problem.
etayluz 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 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 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 helps a lot! appreciate it
dsaxena 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 its because of the typo error i guess
"static int count=0;" is right not "static in count=0;"
irfaan_k97 That and the compiler may require you to initialize the static variable count outside of the method (i.e., before it).
vivekimsit 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 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 no need for the "count--" in the second if statement.
vkrrocky 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 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?
ManLikeZahid 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 thanks
145giakhang 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 Thank youu , That helped me a lot ;)
onuremreerol 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_ beautiful solution
iam_ghanshyam Nice !
vishal_sati Awesome!!!
prendergast And it produces memory leaks!
ace_dexter 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 [deleted]
peterkirby [deleted]
gonca I really like the simplicity and efficiency of your solutions, bravo.
Herat_Patel Thanks man...!
RavikiranCK 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 Excellent thinking. Making the right node null. I am kicking myself for not thinking of this before.
blackL 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 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 That would kill this scenario:
1 / \ 2 3 \ 4 \ 5 \ 6Top view of the above binary tree is 2 1 3 6
dennysregalado 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 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 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 Your are very good!! Perfect Solution
entropyjx 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 [deleted]shashi85 [deleted]shashi85 [deleted]
heisenberg_ab Woah, the simplest and best solution to this problem! I didnt think of this that way...
gonsalespalazio Very clever. :) Thank you.
ambitious_girl What's the logic you used in order to develop it? Thank you!
davidwihl 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 [deleted]jae_duk_seo this solution is amazing and graceful
aalapmaru41 Can someone please explain this code? Thank you
calpang_dev Think of it this way, this problem is asking you to traverse the binary tree in order. That is, left subtree, root, and right subtree - except that you skip the right nodes of the the left subtree, and similarly, you skip the the left nodes of the right subtree.
Now to the code...
Basically, another function is used with an extra parameter that takes an int --> top_view(Node root, int side). The purpose of the side is precisely skip the right nodes of the left subtree, and the left nodes of the right subtree thus the ' top view '.
This overloaded function first checks that root is not null. Then it continues to traverse down the left until it cannot go any further and then starts printing out the values. The recursion unravels until the root is reached at which point the right subtree is traversed. The challenge here is to skip the left nodes of the right subtree. To do this, the recursion function is called with the int 'sides' with values -1, and 1. This allows the recursive calls to skip the right nodes of the left subtree and the left nodes of the right subtree.
It's alot easier to understand after you understand the problem.
AquisBlue passes only one testcase
rajatbarman The most clever solution I found here :)
Shivan111 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 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 [deleted]
rupav Thanks, theses conditions made my submission correct(and i know why)... i used unordered_map to do the same.
rajesh_kashyap60 oh my god! how did u think ?
vuleenguyen_92 Your solution is very good. Thanks
mequint2000 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 amazing bro nice idea
kyxap it works only for 1st TC. Not sure if there changed something
evanadams28 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 [deleted]jittenddra perfect adams very good solution
Ridhuvarshan 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_ Maybe, you called rightview recursively before printing data
rajatshukla wow man ..
umbertodovidio Really nice, I made something similar using a stack. But I think using the recursion stack is much more elegant and beautiful
Shruti165 work well
saifulcseng 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 this was crazy. New people here, don't fall for the top rated comments. instead fall for the newer comments here. seems that testcases got better, and the tougher definition of top view is needed to get an AC here.
pulikutti Python has not been enabled for this challenge!
DanHaggard Adding my +1 for the python version.
w0203j +1 for Python3
daponster [deleted]sumith_gannarapu +1 for Python3
juharri3 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 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 A stack seems overdoing it in terms of space complexity, it may be less elegant, but more practical to print in place.
mequint2000 Not necessarily - using recursion does the same thing; mandarpathak just decided to use his own stack instead of the system stack.
joseph91 1 / \ 2 3 \ 4 \ 5 \ 6Top view of the above binary tree is 2 1 3 6
How about this sample?
Mingling94 It is not, that example would be 213. Only the topmost left and right nodes of a tree are in the topview.
joseph91 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 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 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 [deleted]vinayinusa 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 - 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 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.infoand 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 I think there is problem with their hidden cases.
Sridhar_CR I too hope there is a bug in this
IamSarthak Yeah people are saying that even editorial solution not working
notesalt yes, they aren't working
Sort 591 Discussions, By:
Please Login in order to post a comment