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.
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.
Tree : Top View
You are viewing a single comment's thread. Return to all comments →
C solution using recursion without any additional functions with time complexity of O(N) and 0 space complexity. It's the shortest solution on this forum, but it does alter the tree.
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