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:
Post a Comment