As it seems to me this can be solved like this Find LCA(Least common ancestor) of node x and z .. See if it equals y or not . If not recursively search for y in left and right subtree of LCA ..If you find y in the descendents of LCA answer is true else its false .
This method will give perfect answer just that complexity would be a bit large (greater than n) but space wll be O(1) neglecting stack space during recursive calls I coded the same and it works to me .. If anyone can suggest a finer approach that wud be great :) Regards Ankur On Thu, Nov 24, 2011 at 11:28 PM, Nitin Garg <nitin.garg.i...@gmail.com>wrote: > Please explain what do you mean by 'path between x and z'. > > > On Wed, Nov 23, 2011 at 11:46 PM, Ankuj Gupta <ankuj2...@gmail.com> wrote: > >> There is a binary tree (Not a BST) in which you are given three nodes >> X,Y, and Z .Write a function which finds whether y lies in the path b/ >> w x and z. >> >> -- >> 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. >> >> > > > -- > Nitin Garg > > "Personality can open doors, but only Character can keep them open" > > -- > 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.
