Algorithm:

  1. Check if root is not null if yes return null
  2. check if p or q is direct child of root if yes root is the LCA
  3. find lca for the l =root->left and r =root->right
  4. if l & r are present then root is the LCA else return l or which ever is not null

 

treeNode findLCA(root, p , q)
{
if (!root) return null;
// if either p or q is direct child of root then root is LCA.
if(root->left==p || root->left==q || root->right ==p || root->right ==q) {
return root;
}
else
{
// get LCA of p and q in left subtree.
treeNodePtr l=findLCA(root->left , p , q);

// get LCA of p and q in right subtree.
treeNodePtr r=findLCA(root->right , p, q);

// if one of p or q is in leftsubtree and other is in right
// then root it the LCA.
if(l && r) {
return root;
}
// else if l is not null, l is LCA.
else if(l) {
return l;
} else {
return r;
}
}
}

Advertisements