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
> > 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.
>
>
--
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.
