Tuesday, October 4, 2011

Find Least Common Ancestor of two nodes in a Binary Tree


Node* BSTree::LCA(Node* node, int num1, int num2)
{
if(!node)
return NULL;
else
{
if(node->data == num1 || node->data == num2)
return node;
else
{
Node* leftLCA = LCA(node->left, num1, num2);
Node* rightLCA = LCA(node->right, num1, num2);
if(leftLCA && rightLCA)
return node;
else if(leftLCA)
return leftLCA;
else if(rightLCA)
return rightLCA;
   else
    return NULL;
}
}
}

No comments:

Post a Comment