Least Common Ancestor (LCA) of a BST & Binary Tree

The least Common Ancestor is one of those problems which appear quite complicated, but is pretty straightforward and can be solved easily.
 So in this blog, we're going to understand how to find LCA in a BST & a Binary Tree.

Given a binary tree and two nodes n1=1 & n2=4, so the first common node for n1 & n2 with the minimum difference in their heights is 3, therefore 3 is the LCA for n1 & n2.

Let's discuss where cases to make you understand LCA better:
For n1 = 2, n2 = 3  LCA=> 3
For n1 = 4, n2 = 8  LCA=> 5
For n1 = 7, n2 = 9  LCA=> 8

So now let's try to find LCA in a Binary Search Tree:
In a binary search tree, the elements to the left of the root are smaller than the root, and elements to the right of the root are greater than the root.
We can find the LCA according to the following conditions :
Both n1 & n2 are smaller than the root so, LCA will be in the left sub-tree.
Both n1 & n2 are greater than the root so, LCA will be in the right sub-tree.
Otherwise, the root will be the LCA.

Implementation :

Node *lca_bst(Node *root,int n1,int n2)
{
    while(root!=NULL)
    {
        if(root->data>n1 && root->data>n2)
            root=root->left;
        else
        if(root->data<n1 && root->data<n2)
            root=root->right;
        else
            break;
    }
return root;
}

Similarly for Binary Trees also we can have the following conditions:
If n1 == root or n2 == root then LCA => root
We'll look for n1/n2 recursively in Left Subtree & Right Subtree.
If we get a not null value from left subtree's node & right subtree's node then we'll return root as LCA.
Otherwise, if left subtree's node is not null then return left subtree as LCA else return right subtree's node.
Implementation :

// Lca for Binary Tree
Node * lca(Node* root,int n1,int n2)
{
    // base case
  if(root==NULL)
    return NULL;

  // If either n1 or n2 matches with root's key, report 
  // the presence by returning root (Note that if a key is 
  // ancestor of other, then the ancestor key becomes LCA 
  if(root->data==n1 or root->data==n2)
    return root;
    
  // Look for keys in left and right subtrees
  Node *l = lca(root->left,n1,n2);
  Node *r = lca(root->right,n1,n2);
  
  // If both of the above calls return Non-NULL, then one key
  // is present in once subtree and other is present in other, 
  // So this node is the LCA 
  if (l and r)
    return root;

  // Otherwise check if left subtree or right subtree is LCA
  return (l!=NULL)?l:r;
}

I hope this tutorial helped you!

Happy Coding!