This approach would fail in certain cases :P..in fact lot many cases :D..It needs to be modified using space
The thing is while calculating LCA we must also store the path in an Array or vector and then Iterate over its elements to check if match occurs. Cant think of O(1) solution though :( On Fri, Nov 25, 2011 at 12:57 AM, Ankur Garg <ankurga...@gmail.com> wrote: > 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.
