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
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
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 :(
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
