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.
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.
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.
Tree : Top View
You are viewing a single comment's thread. Return to all comments →
Simple version.
I came up with a similar solution in Java :) So far, I like it the most.
Your are very good!! Perfect Solution
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.
Woah, the simplest and best solution to this problem! I didnt think of this that way...
Very clever. :) Thank you.
What's the logic you used in order to develop it? Thank you!
I independently came up with a similar solution for Python:
this solution is amazing and graceful
Can someone please explain this code? Thank you
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.
passes only one testcase
The most clever solution I found here :)
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.
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
Thanks, theses conditions made my submission correct(and i know why)... i used unordered_map to do the same.
oh my god! how did u think ?