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.
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.
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.
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...
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
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?
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.
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.
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.
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.
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}.
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.
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.
Tree : Top View
You are viewing a single comment's thread. Return to all comments →
Will this solution work for the below input?
I guess "11" will not be printed in spite of it being visible, as the branch containing 9 will not be traversed?
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.
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); } }
Exactly. I am looking for a perfect soluction for this problem.
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.
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...
Hope this helps, used a static count variable
void top_view(node * root) {
}
helps a lot! appreciate it
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???
its because of the typo error i guess
"static int count=0;" is right not "static in count=0;"
That and the compiler may require you to initialize the static variable count outside of the method (i.e., before it).
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?
Corresponding Java Solution, Thanks it was easy to understand :).
static int count=0;
void top_view(Node root){
}
no need for the "count--" in the second if statement.
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..
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?
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.
thanks
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
Thank youu , That helped me a lot ;)
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.
beautiful solution
Nice !
Awesome!!!
And it produces memory leaks!
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.
I really like the simplicity and efficiency of your solutions, bravo.
Thanks man...!
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; }
}
Excellent thinking. Making the right node null. I am kicking myself for not thinking of this before.
i think you alter the tree;,my answer:
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.
That would kill this scenario:
Top view of the above binary tree is 2 1 3 6
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}.
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 ?
Your solution is very good. Thanks
@Sadesh, why is it that you are passing goLeft to
top_viewin the else part as a parameter along with node.right?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.
amazing bro nice idea
it works only for 1st TC. Not sure if there changed something