We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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:
When I visited this question there was no definition for top view given so I had to search for a definition. I came to the geeks for geeks link that others have referenced and made my algorithm according to geeks for geeks' definition which is the same as @Faland's and it was still accepted no problem. There was also only two test cases when I submitted. I honestly think you can submit either way and be fine unless my submission is not implementing geek for geek's definition of top view correctly.
You are spot onn in identifying two different implementations .. looks like this question demands just the outer values of the tree. Thanks once again.
Isn't it the second solution that is expected - the first solution passes in July '18! Seems like they changed the meaning; and if so, I don't think this is a "easy" problem - a "medium" one.
it seems the second part of parmarabhishek_1's post was what the problem originally expected, and that was incorrect. They changed it to correctly require the solution in the first part, as you pointed out. They should have also used a better example to illustrate this subtle point.
Yep, the definition of "Top-View" was never presented in this problem. Besides the grammatical errors in the sentence "explaining" top-view, it almost literally says: when you view from the top, you'll see the top view.
The definition I found, that made sense was from the geeks for geeks link. So I solved it that way. I failed everything past the first test. So I looked at the input/output for the second test case.
For anyone interested, it's clear that the input is given as a binary search tree. So I constructed the graph from the input, ran my program, got the correct result but with extras (to the right for the second test case).
Then figured I was getting extras because a subtree was "poking" out and they didn't want that. So deleted all of my (more complicated) code for what amounted to a trivial problem.
If you hover of the submission results that failed, there will be a popup that appears, where you can download both the input and expected output for that test case.
You appear to have the correct output, but in the wrong order. The solution wants it "left-to-right" (which just so happens to be least-to-greatest since these are apparently
binary search trees).
The root is 47 (the first node given), the rest are input as a binary search tree, which means 2 is the left child of 47. 40 is the right child of 2 (because it's less than 47 but greater than 2), 20 is the left child of 40 (less than 47, greater than 2, and less than 40)...etc.
Exactly!!
Even i got that the other way..
I coded the solution considering the horizontal distances of the nodes and all my test cases(except the sample case) failed!
The actual top view certainly is different than what they expects!
no , by the way it become more easy that way u just have to traverse left and store all in vector(push tis data from front) then just traverse right and store it in same vector(push this data from back) then simply print the data or u can use recurssion :)
Isn't the my shown diagram show uniformness according to your design? You just broadened the root, if you broaden the root, you will also have to broaden others equally. So its answer will be 4,2,1,3,7
if you only have same space everywhere how can you add left child of 3, so really parents have twice width of branch then children so all the nodes can be set.
@alex_mistery, I understand what you are saying, however, in my experience, top-view of a binary tree is determined by the combination of Level-Order-Traversal and Vertical-Order-Traversal, in other words, you determine all the nodes that are in the same Vertical-Order but only choose the node in each Order that first appears in the Level-Order list. So when doing this, you get the following...
Level_Order=[1,2,3,4,5,6,7,8]
Vertical-Orders are the following (0 is root position, all others are delta from root)
Since 4, 2, 7, 8 are alone in there set, we don't have to refer to the level order choose. In the 0 and 1 Distances from the root, we have [1,5] and [3,6]. 1 occurs first in Level_order over 5, so we choose 1. 3 occurs first in Level_order over 6, so we choose 3. So after eliminating 5 and 6, going from left-right, we get...
4,2,1,3,7,8
This is the algo used in Geeks for Geeks and is widely used in all documentation of top-view I've seen. So, @Faland is correct in this respect. Intuitively, the alternative where someone only see the higher levels in the top-view without compensating for vertical displacement doesn't make any sense. Think about how a pyramid works. If I were to take @alex_mistery's interpretation, I shouldn't be able to see the outerbricks on the base of a pyramid if I was looking down from the top no matter how far away from the center those bricks were.
I watched a video on Youtube giving the same explanation as you did. However, what confused me is why level order traversal should be referred? Why can't we print the first node for each horizontal distance stored in the Vertical Order traversal dictionary (which is the top node of each HD)?
FYI, there is a problem with this definition. You can have overlap of the "top" nodes. For instance, when looking "to the left", you could have a branch "poke" out that coincides with another branch. In this case both nodes would appear to be at both the same level and height. My assumption (in my solution) for a tie was the the "left-most" branch was the highest--that is the branch that originated from the "most" left position (in this case that would be how I drew it).
how the hell is that supposed to be mathematical?
mathematically a tree is not even a geometric object. and there certainly is no correct way to draw it.
That's not true, you're changing the tree by making the 6 right of the 5. You need to space out those lower levels so 5->6->7->8 still goes to the left, but the 8 is always right of the 2.
Why have you only considered top root like this, why did'nt you made every root level same as the top one ? @Faland is right and geeksforgeeks also refers the same .
According to your explaination,
I you are asked to print the bottom view of the tree then it it will print all the elements of the tree because they are all visible from bottom. But I think this will not be right.
I coded according to this definition, but the test cases failed except the first one.
Here is a custom test case that I used 7 10 4 3 5 6 7 11
10
/ \
4 11
/ \
3 5
\
6
\
7
According the defninition, the output should be 3 4 10 11, and that is what my program also gives, but when I submit the code, except first test case, all other test cases fails
Yeah, the pattern in which they want the output is different from the geeksforgeeks order. The val that is considered there is the horizontal distance, so, here I guess they want the vertical order with the least value of horizontal distance (i.e. the farthest left first).
Yeah, this is the straightforward definition of top view, and at the beginning I think so too. but some test case, and the above explanation break that.
I was left for months, so this situation may changed now.
You can use negative-position array for the nodes in root-left and positive-position array for the nodes in root-right. Using queue, BFS can be used with sending relative position to root. If abs(position) is larger than length of the corrensponding array (if position >0, positive-pos arr, if position <0, negative-pos arr), append the value to corresponding array. If BFS is done, the result is reversed(negative-pos arr) + value_at_zero + positive-pos arr.
The idea is that for each node traversed, if that node has a horizontal distance(distance from the centre of the tree) which no other node has had so far, map that horizontal distance to the value of that node.
It goes down the tree and stores the first nodes which are at all the possible distances from the root
Think of it this way, @marcotuliorr. Imagine if that '3' node had three consecutive children "7 - 8 - 9" (each node is the left child of its parent.) Would that branch cross over the long "4 - 5 - 6" branch and make the top-down view of the tree "9 - 2 - 1 - 3 - 6"? Of course not!
Every node's child must retain the positional properties of its parent, I.E. if 2 is to the left of 1, then 4 and 5 must also be to the left of 1. If 5 is to the left of 1, 6 must be to the left of 1 as well, etc. There's no way a branch not on the leftmost or rightmost path could be visible from the top down.
I think that link is wrong. In a binary tree, once you go left, all descendants of that child are by definition left of that parent. To get an accurate spatial representation you have to expand your tree so that the bottom level will fit if it is full. They say:
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'.
"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.
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.
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.
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!
This problem dosent consider these much cases, it only want you to print left only list and right only list. which can be simply achieved by going extreme left and extreme right. so yeah second is correct for this problem.
I don't think thats how it is!!
According to me the output should rather be : 8 4 2 1 3..
I think all we need is to calculate the horizontal distance of each nodes from the root node and print the node and store them in the queue..then print the first node from the queue for each level of horizontal distance!
Yeah, some more details would be nice, or perhaps using a tree like the OP's examples as one of the problem examples to demonstrate exactly what is meant by "top view". Or just a definition of "top view". I spent quite a while working on a solution that would track how far left and right of center each node was in order to handle a case like the examples above. Then I checked the discussion and realized the problem was way easier than I'd thought.
yeah but technically in your second example it should be 8-4-2-1-3.
I am scratching my head for a very long time , they should really add more explanation
I agree with @Faland.
The problem is not well described.
So, first I searched the internet for top view problem and solved it.
https://www.youtube.com/watch?v=c3SAvcjWb1E
In fact a correctly solved problem failed the test case. So, I calculated manually and my solution was correct.
It took me lot of time to understand that there is meant something else, after looking in this discussion.
So, the problem here is not correctly described. Here is also info about top view:
http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/
Don't cover you with mathematical description. Look through the window, see a tree. What will be the top view of a tree if you cut a branch? Don't cover you with the fact that you can't provide a mathematical description. An algorithm is already a mathematical description, see youtube link. Any tree that is seen through the windows is all maths.
That is just an artifact of how you draw the tree. By definition, everything left of the 1 is left of the 1. To accurately draw your tree, the 3 needs to be right of the 1 and all nodes in the left branch from the 1 should be displayed left of the 1.
This isn't easy to see in the examples because you have a sparse tree, but if you leave enough rooms for the bottom level to be full, you can see why:
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.
LOL. I solved it for the graphical case first and thought that it was at least medium level problem. Now I see that it's a simpler problem. Thanks @Faland
I am a beginner. If I found this place earlier, I would have not spent hours on this unclarified 'easy' question and doubt myself......
In conclusion, two interpretations on this question:
1. Just like what @thedurphy said, this interpretation of top view aligns with this Youtube video and GFG. And code in Python can be like this (Although it does not pass all tests, it aligns with first interpretation):
deftopView(root):fromcollectionsimportdefaultdictqueue=[(root,0)]hashtable=defaultdict(lambda:[])fornode,levelinqueue:#level=x-coordinatorifnode!=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 queueifhashtable!=None:forlevelinxrange(min(hashtable.keys()),max(hashtable.keys())+1):printhashtable[level][0],#TOPVIEWelse:returnNone
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:
deftopView(root):#start with left most leafifroot.left:printleftside(root.left)#print left side top view, from bottom to top (left to right)printroot.data,#print rootifroot.right:printrightside(root.right)#print right side top view, from top to bottom (left to right)defprintleftside(node):ifnode:printleftside(node.left)else:returnprintnode.data,defprintrightside(node):ifnode:printnode.data,printrightside(node.right)else:return
In the end, WHAT do we use TOPVIEW for in terms of both interpretations?
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.
// where n is the number of nodes in the binary tree
public static void topView(Node root) {
int MAX = 500; // Otherwise, MAX=getNodeCount(root);
int[] top = new int[MAX*2];
Queue<Object[]> queue = new ArrayDeque<>();
queue.add(new Object[]{root, MAX});
while(!queue.isEmpty()) {
Object[] array = queue.remove();
Node node = (Node)array[0];
Integer order = (Integer)array[1];
if(node == null) continue;
if(top[order] == 0) top[order] = node.data;
queue.add(new Object[]{node.left, order-1});
queue.add(new Object[]{node.right, order+1});
}
for(int data: top) if(data != 0) System.out.print(data + " ");
}
Here's the Java code, I used the approach from geekstogeeks. I think the question did not specifiy and clearly define what a top view is. The correct implementation which passes all test cases should be according to this https://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/.
Tree : Top View
You are viewing a single comment's thread. Return to all 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:
Expected: 4-2-1-3-7 ? In fact - 4-2-1-3.
Expected: 8-4-2-1-3 ? In fact - 4-2-1-3, again.
It is just your visual perseption of the tree! The truth is that mathematically it looks like this:
when top view of the tree is asked, which one is meant among the two?
Just as @AlexMistery explained
If the other was true, it would be much tougher to code. Isn't that?
no only printing of leaves will be added
This problem expects solution as @AlexMistery explained.
But the actual Top view seems to be different though.
When I visited this question there was no definition for top view given so I had to search for a definition. I came to the geeks for geeks link that others have referenced and made my algorithm according to geeks for geeks' definition which is the same as @Faland's and it was still accepted no problem. There was also only two test cases when I submitted. I honestly think you can submit either way and be fine unless my submission is not implementing geek for geek's definition of top view correctly.
If we follow algo given by geeksforgeeks then it doesnt give right answer. Geeks for geeks alfo print according @Faland
It Does, I have submitted the logic of vertical order traversal.
This is the actual code for top view of a tree :
but the problem demands the top view according to the root node only :
You are spot onn in identifying two different implementations .. looks like this question demands just the outer values of the tree. Thanks once again.
Isn't it the second solution that is expected - the first solution passes in July '18! Seems like they changed the meaning; and if so, I don't think this is a "easy" problem - a "medium" one.
it seems the second part of parmarabhishek_1's post was what the problem originally expected, and that was incorrect. They changed it to correctly require the solution in the first part, as you pointed out. They should have also used a better example to illustrate this subtle point.
it's not working for all the test cases
I think you are printing root->data 3 times in the topView() function.
no he cancelled out repetitions by using root->left and root->right as initializers in the two functions
Yep, the definition of "Top-View" was never presented in this problem. Besides the grammatical errors in the sentence "explaining" top-view, it almost literally says: when you view from the top, you'll see the top view.
The definition I found, that made sense was from the geeks for geeks link. So I solved it that way. I failed everything past the first test. So I looked at the input/output for the second test case.
For anyone interested, it's clear that the input is given as a binary search tree. So I constructed the graph from the input, ran my program, got the correct result but with extras (to the right for the second test case).
Then figured I was getting extras because a subtree was "poking" out and they didn't want that. So deleted all of my (more complicated) code for what amounted to a trivial problem.
can anyone explain how to represent the tree for this input, 47 2 40 20 38 30 14 28 10 16 19 44 39 27 7 9 31 12 43 21 5 41 34 49 13 33 3 4 25 22 29 15 32 35 6 24 23 26 1 11 42 36 37 17 18 8 45 48 50 46 ? what is root of this tree ?
same question.. Expected output: 1 2 47 49 50 My output: 47 2 1 49 50
@niranjan_wad how did you manage to find the output? Since, it does not tell what is your output. do you know what is root of above question ?
If you hover of the submission results that failed, there will be a popup that appears, where you can download both the input and expected output for that test case.
You appear to have the correct output, but in the wrong order. The solution wants it "left-to-right" (which just so happens to be least-to-greatest since these are apparently binary search trees).
Try using TreeMap so the keys will be in sorted order
bro..first print traverse, then print that node. then u get correct order
first traverse,the print that node. u get correct order
The root is 47 (the first node given), the rest are input as a binary search tree, which means 2 is the left child of 47. 40 is the right child of 2 (because it's less than 47 but greater than 2), 20 is the left child of 40 (less than 47, greater than 2, and less than 40)...etc.
Exactly!! Even i got that the other way.. I coded the solution considering the horizontal distances of the nodes and all my test cases(except the sample case) failed! The actual top view certainly is different than what they expects!
No! an entire branch could appear in the top view. not just the leaves.
Not much tough though. I wrote the code with that assumption only. Problem writers need to do a better job here.
no , by the way it become more easy that way u just have to traverse left and store all in vector(push tis data from front) then just traverse right and store it in same vector(push this data from back) then simply print the data or u can use recurssion :)
how can you push sometrhing from front in a vector
vec.push_front(data);
but if this case1 , the top view not see
"truth". If that's a mathematical truth show your proof.
If you add underscores to root, why not to all elements?
Isn't the my shown diagram show uniformness according to your design? You just broadened the root, if you broaden the root, you will also have to broaden others equally. So its answer will be 4,2,1,3,7
Reference: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/
if you only have same space everywhere how can you add left child of 3, so really parents have twice width of branch then children so all the nodes can be set.
i have the same question .This case will definitely leads to failure of our logic
Mathematically it's what you define it to be, and the exercise's woding is wide open to interpretation.
really awesome!!
http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/
@alex_mistery, I understand what you are saying, however, in my experience, top-view of a binary tree is determined by the combination of Level-Order-Traversal and Vertical-Order-Traversal, in other words, you determine all the nodes that are in the same Vertical-Order but only choose the node in each Order that first appears in the Level-Order list. So when doing this, you get the following...
Vertical-Orders are the following (0 is root position, all others are delta from root)
Since 4, 2, 7, 8 are alone in there set, we don't have to refer to the level order choose. In the 0 and 1 Distances from the root, we have [1,5] and [3,6]. 1 occurs first in Level_order over 5, so we choose 1. 3 occurs first in Level_order over 6, so we choose 3. So after eliminating 5 and 6, going from left-right, we get...
This is the algo used in Geeks for Geeks and is widely used in all documentation of top-view I've seen. So, @Faland is correct in this respect. Intuitively, the alternative where someone only see the higher levels in the top-view without compensating for vertical displacement doesn't make any sense. Think about how a pyramid works. If I were to take @alex_mistery's interpretation, I shouldn't be able to see the outerbricks on the base of a pyramid if I was looking down from the top no matter how far away from the center those bricks were.
I watched a video on Youtube giving the same explanation as you did. However, what confused me is why level order traversal should be referred? Why can't we print the first node for each horizontal distance stored in the Vertical Order traversal dictionary (which is the top node of each HD)?
FYI, there is a problem with this definition. You can have overlap of the "top" nodes. For instance, when looking "to the left", you could have a branch "poke" out that coincides with another branch. In this case both nodes would appear to be at both the same level and height. My assumption (in my solution) for a tie was the the "left-most" branch was the highest--that is the branch that originated from the "most" left position (in this case that would be how I drew it).
Now, that's some Editorial-grade insight take notes, lads!
how the hell is that supposed to be mathematical? mathematically a tree is not even a geometric object. and there certainly is no correct way to draw it.
agreed :)
That's not true, you're changing the tree by making the 6 right of the 5. You need to space out those lower levels so 5->6->7->8 still goes to the left, but the 8 is always right of the 2.
nice explanation
Thanks, checking the level sign i was able to solve this problem
Doesnt work
Why have you only considered top root like this, why did'nt you made every root level same as the top one ? @Faland is right and geeksforgeeks also refers the same .
we should have level orders from top(root). So according to this question, we can only consider for root alone.
1 / \ 2 3 \ 5 / \ 4 6 \ 7 \ 8
the diagrams of the problem should have been drawn like this in order not to create ambiguity.
note that this is no longer true; the problem has been changed to the exact opposite!
According to your explaination, I you are asked to print the bottom view of the tree then it it will print all the elements of the tree because they are all visible from bottom. But I think this will not be right.
I coded according to this definition, but the test cases failed except the first one.
Yeah, the pattern in which they want the output is different from the geeksforgeeks order. The val that is considered there is the horizontal distance, so, here I guess they want the vertical order with the least value of horizontal distance (i.e. the farthest left first).
I am really confused with the
top view
definition. And do not agree with this explaination.For case:
It expects:
but not:
exact same issue I am having.
from what I understand, the top view outputs should be in ascending order. but the expected answers from the tests seem to break this rule.
you may check this https://www.youtube.com/watch?v=c3SAvcjWb1E
Yeah, this is the
straightforward
definition 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.
In that case, why in test case 2 (input 1 14 3 7 4 5 15 6 13 10 11 2 12 8 9) is the expected output 2 1 14 15 12 and not 1 14 15?
I think you have the same problem as me with what they mean by top-view but I'd like to point out some tiny improvements to your code.
Storing outputs in a vector is a pointless inefficiency. You can cout in your loops instead of pushing the values to a vector that prints after.
You can use negative-position array for the nodes in root-left and positive-position array for the nodes in root-right. Using queue, BFS can be used with sending relative position to root. If abs(position) is larger than length of the corrensponding array (if position >0, positive-pos arr, if position <0, negative-pos arr), append the value to corresponding array. If BFS is done, the result is
reversed(negative-pos arr) + value_at_zero + positive-pos arr
.C++ solution :
eplain hd[root->data]=root->data; if (!m[hd[root->left]]) m[hd[root->left]] = root->left->data;
The idea is that for each node traversed, if that node has a horizontal distance(distance from the centre of the tree) which no other node has had so far, map that horizontal distance to the value of that node.
It goes down the tree and stores the first nodes which are at all the possible distances from the root
Can't we say print all left most and right most elements of root node ?
I think Faland is right. This link correctly defines tree top view: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/
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.
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.
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:
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'.
YES, I'm also confused: what's top view......
Dont agree with this problem being tagged as "Easy".
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.
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/
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.
I just read your comment and solved it in 60 sec. Thanks very much :)
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
you are right.
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.
this will only pass the 1st test case. i thougth the same logic and i implemented it in c++.
Will not pass the 2nd TCs :)
This only passes the sample and first test case
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!
took me two minutes to solve
can you please send me the code Mr tvanloon.I am basic coder please....:)
Its better(learning-wise) to ask for a problem-solving approach instead of solutions.
8 4 2 1 3
This problem dosent consider these much cases, it only want you to print left only list and right only list. which can be simply achieved by going extreme left and extreme right. so yeah second is correct for this problem.
The issue is that the problem is poorly defined. You are correct, but that isn't clear from the problem statement.
I don't think thats how it is!! According to me the output should rather be : 8 4 2 1 3.. I think all we need is to calculate the horizontal distance of each nodes from the root node and print the node and store them in the queue..then print the first node from the queue for each level of horizontal distance!
Had the same expectation after reading the problem statement. Glad I came here before wasting a bunch of time and getting frustrated.
I agree the problem statement needs more examples.
Thanks. My submission failed but when I looked into why it was pretty clear I only a vague/foggy notion of 'top view'.
Thank you I didnt want to cheat but this makes the problem much easier.
Yeah, some more details would be nice, or perhaps using a tree like the OP's examples as one of the problem examples to demonstrate exactly what is meant by "top view". Or just a definition of "top view". I spent quite a while working on a solution that would track how far left and right of center each node was in order to handle a case like the examples above. Then I checked the discussion and realized the problem was way easier than I'd thought.
yeah but technically in your second example it should be 8-4-2-1-3. I am scratching my head for a very long time , they should really add more explanation
I agree with @Faland. The problem is not well described. So, first I searched the internet for top view problem and solved it. https://www.youtube.com/watch?v=c3SAvcjWb1E In fact a correctly solved problem failed the test case. So, I calculated manually and my solution was correct. It took me lot of time to understand that there is meant something else, after looking in this discussion. So, the problem here is not correctly described. Here is also info about top view: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/ Don't cover you with mathematical description. Look through the window, see a tree. What will be the top view of a tree if you cut a branch? Don't cover you with the fact that you can't provide a mathematical description. An algorithm is already a mathematical description, see youtube link. Any tree that is seen through the windows is all maths.
That is just an artifact of how you draw the tree. By definition, everything left of the 1 is left of the 1. To accurately draw your tree, the 3 needs to be right of the 1 and all nodes in the left branch from the 1 should be displayed left of the 1.
This isn't easy to see in the examples because you have a sparse tree, but if you leave enough rooms for the bottom level to be full, you can see why:
If you go on and add 7 left of 6 and 8 left of 7, you add two new levels to the tree, and you'll have to space it out to handle all the other nodes possible at that level. No matter what you do, everything right of the 2 will be right of the 2, and left of the 1, being shaded to the link from 1 to 2.
Since the question mentions it is a binary tree, this possibility is ruled out. chect out this link for the properties of binary trees.
http://cs-study.blogspot.in/2012/11/properties-of-binary-tree.html
Yes, I have the same comfusion. And I write a code below: void topView(Node root) { if(root!=null) { Set s = new HashSet(); LinkedList queue = new LinkedList(); Map map = new HashMap(); queue.offer(root); map.put(root.data, 0); while(!queue.isEmpty()) { Node node = queue.poll(); Integer shadow = map.get(node.data); if(!s.contains(shadow)) { System.out.print(node.data + " "); s.add(shadow); } if(node.left != null) { queue.offer(node.left); map.put(node.left.data, shadow-1); } if(node.right != null) { queue.offer(node.right); map.put(node.right.data, shadow+1); } } } }
Very important details and see the below alex_mistery's comment!
LOL. I solved it for the graphical case first and thought that it was at least medium level problem. Now I see that it's a simpler problem. Thanks @Faland
I am a beginner. If I found this place earlier, I would have not spent hours on this unclarified 'easy' question and doubt myself...... In conclusion, two interpretations on this question: 1. Just like what @thedurphy said, this interpretation of top view aligns with this Youtube video and GFG. And code in Python can be like this (Although it does not pass all tests, it aligns with first interpretation):
In the end, WHAT do we use TOPVIEW for in terms of both interpretations?
your code is just passing first test https://pastebin.com/CmTWX5C1
My solution
this code is only passing the test case 1
here top view means:==>>
Enjoy..
The problem has been changed now . New ans for above would be as expected i.e., 4-2-1-3-7
I feel like this makes the problem quite a bit harder, I don't think it should still be marked as "easy".
Thanks a lot Faland. People confuse for this representation. I retried this question after 3 years and again forgot.
Yes it should be based on horizontal distance from root node. Refer to https://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/
Thanks for the small examples to visualize. This help alot.
This problem looks like we need to generate horizontal, depth pair for each node, then group them by horizontal coordinate, and just collect the minimum depth from each group.
For problem statement:
1 (0, 0) 2 (1, 1) 5 (2, 2) 6 (3, 3) 3 (1, 3) 4 (2, 4)
1 (0, 0)
2 (1, 1) 3 (1, 3)
5 (2, 2) 4 (2, 4)
6 (3, 3)
solution pass all test cases
If we take the tree as in Faland's comment.
The answer for which the compiler successfully runs the test is 4-2-1-3-7
and for
output is 8-4-2-1-3 which compiler accepts.
You may refer geeks for geeks for the top view.
Java Solution in O(n)
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/.
You understand ,in this question we are talking about Binary tree?? What kind of explanation have you given here??