@anika this solution only works for BST
On Mon, Aug 15, 2011 at 4:20 PM, Anika Jain <[email protected]> wrote:
> node *common_ancestor(node *root, node **prev, int x,int y)
> {
> if(root->a==x || root->a==y)
> return *prev;
> else if(root->a > x && root->a > y)
> {
> prev=&root;
> return common_ancestor(root->l,prev, x,y);
> }
> else if(root->a < x && root->a < y)
> {
> prev=&root;
> return common_ancestor(root->r,prev, x,y);
> }
> else
> {
> prev=&root;
> return *prev;
> }
> }
>
> with call as
> node *prev=NULL;
> common_ancestor(root,&prev,x,y);
>
>
> On Sun, Aug 14, 2011 at 10:08 PM, Yasir <[email protected]> wrote:
>
>> Guys, How about the below mentioned implementation?
>> The only assumptions is that nodes should exist in the tree. (will fail
>> if one node exists and another doesn't)
>>
>> static Node LCA(Node root, int d1, int d2){
>> if(root==null)
>> return root;
>> if(root.left!=null && ( root.left.data == d1 || root.left.data==d2 ) )
>> // both nodes exists in left sub-tree
>> return root;
>>
>> if(root.right!=null && ( root.right.data == d1 || root.right.data==d2) )
>> // both nodes exists in right sub-tree
>> return root;
>> Node ltree = LCA(root.left, d1, d2); //check recursively in left
>> subtree
>> Node rtree = LCA(root.right, d1, d2); // check recursively in
>> right subtree
>> if(ltree!=null && rtree!=null) // One node in left & another in right
>> return root;
>> return (ltree==null)?rtree:ltree;
>> }
>>
>>
>> Just to mention that, closest ancestor of 5&4 OR 4&9 would be 3 in the
>> following tree:
>> 3
>> \
>> 4
>> / \
>> 5 8
>> /
>> 9
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/24JUUQsBHvIJ.
>>
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
