@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
> returned....all 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.
