Re: [algogeeks] Re: Find the path in two nodes of a binary search tree
@shashank : i am not sure if i am getting it right but are you saying save address of 2 nodes. now do inorder traversal considering node1 as the starting point , during traversal if we find node2 then return. if that so , then i dont think so it will work for all the cases. please correct me if i am wrong. On Thu, Jan 5, 2012 at 3:55 PM, WgpShashank shashank7andr...@gmail.comwrote: @top coder , if its given that that you have to nodes as input , 1st find the two nodes , store their address then do any traversal to get the path between them , inorder will good . i ams assuming you wants to print the path between two such nodes. hope it suffices :) let me know if approach it not clear or i missed something . Thanks Shashank Mani Computer Science Birla Institute of Technology,Mesra *http://shashank7s.blogspot.com* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/0jnGdn-_vZgJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find the path in two nodes of a binary search tree
@atul ,, why it won;t work , any clarification ? Thanks Shashank Mani Computer Science Birla Institute of Technology,Mesra *http://shashank7s.blogspot.com* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/MAy1c62BN9cJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find the path in two nodes of a binary search tree
1) suppose node1 is at level = 4 of the tree and node2 is at level = 3 of the tree if you do inorder traversal from node1 i.e calling function inorder(node1); now it will search form level 4 to the max depth of the tree it will never reach node2 because it is at level = 3. 2) suppose root of the tree is X node1 lies of the left subtree of the root and node2 lies on the right subtree of the root. now after saving address of node1 and node2 , you start inorder traversal at node1 or at node2. suppose if you call inorder(node1); it will search node2 in the left subtree of the root X...taking node2 as a root of the traversal , but node2 lies on the right subtree of root X. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find the path in two nodes of a binary search tree
@Lucifier : nice solution for problem 2. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find the path in two nodes of a binary search tree
for problem 1, simply keep an array and counter of length of tree, pass it
in each recursive call,
when you find the required node, just print the array and exit.
if not clear, then i will post the code.
@lucifier
for problem 2 nice solution
On Mon, Jan 2, 2012 at 10:56 PM, Lucifer sourabhd2...@gmail.com wrote:
@topcoder..
Problem 1:
Say we are doing an inorder traversal..
All we need to do is once the required node X is found.. we will stop
the recursion..
The recursion can be stopped by using a bool value..
Basically the bool value will indicate - no further processing
required..
While the recursion loop rolls back we will just record the nodes
while rolling back..
The point being that,
Say currently we have reached a given node X, then the recursion stack
actually stores states mimicing the shortest path from root to that
node..
As mentioned above, once we record the nodes while rooling back..Say
the sequence is S.
Reverse(S) will give u the path...
Problem 2:
Apply the above algo for nodes A and B,
Say the sequences are S1 and S2,
All we need to do is :
Find common substring starting at index 0 for Rev(S1) and Rev(S2)
Now, subtract the common substring from Rev(S1) and Rev(S2)..
Say, after subtraction its M1 and M2
Also record the last char of the common substring..Say N
The path from A to B would be concat (Rev(M1), N, M2)
On Jan 2, 9:50 pm, Abhishek Gupta guptaabhishe...@gmail.com wrote:
we might implement it using recursive calls where once found..the node is
printed and true is returned and if leaf is reached...false is
returnedall the function calls getting true will again print and
return
true...and false will just return false without printing...this way we
can
print only nodes which are in path from root to target node...i can
assume
it to be a simple binary seach tree...
On Mon, Jan 2, 2012 at 10:12 PM, top coder topcode...@gmail.com wrote:
Suppose you have a tree. A binary tree (for something like
simplicity :p). You are traversing it (using infix, postfix or prefix)
to search for a node. You find your required node. You just realized
that you need to know the path from this node back to the root node
(and/or vice versa). Given the following description of the structure
of the tree node that you “cant” change:
struct node{Data data; node *right,*left;};
what will you strategy be to tackle this problem.
To make it more intresting (or maybe just the application of the above
problem) suppose you find the node A and a node B in consecutive
searches. Now what will your strategy be to show a path from A to B.
(not neccesarily from the root of the whole tree, but possibly).
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Abhishek Gupta
BITS, Pilani
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
