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.
