find least common ancestor in Binary search tree


Q)least common ancestor for binary search tree

recursive way of doing is here. In BST, all values lesser than root will be on left subtree, values greater than root will be on right subtree.

node *ancestor=NULL

node * LCA(node *root,node *n1, node*n2)
{

if(n1 == NULL && n2 == NULL)
  return root ;

if(n1 == NULL)
 return n2;

if(n2==NULL)
  return  n1 ;

return findLCA(root,n1,n2) ;
}

node *findLCA(node *root,node *n1,node *n2)
{
ancestor=root;

if(n1->data < root->data && n2->data < root->data)
 return LCA(root->left,n1,n2)
else if(n1->data > root->data && n2->data > root->data )
return LCA(root->right,n1,n2)
else
return ancestor;

}

No comments: