Lowest Common Ancestor in a Binary Tree

Lowest Common Ancestor (LCA)

The lowest common ancestor of two nodes p and q in a binary tree is the deepest node that is an ancestor of both p and q. A node can be an ancestor of itself.

LCA in a General Binary Tree

LCA(root, p, q):
  if root is NULL: return NULL
  if root == p or root == q: return root
  left  = LCA(root.left, p, q)
  right = LCA(root.right, p, q)
  if left != NULL and right != NULL: return root  // p and q are in different subtrees
  return left if left != NULL else right

Example

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

LCA(5, 1) = 3  (5 is in left, 1 is in right → root 3 is LCA)
LCA(5, 4) = 5  (4 is a descendant of 5 → 5 is LCA)
LCA(6, 4) = 5  (both in left subtree, both under 5)

LCA in a BST (Optimized)

In a BST, you can exploit the ordering property:

LCA_BST(root, p, q):
  if p.value < root.value and q.value < root.value:
    return LCA_BST(root.left, p, q)   // both in left subtree
  if p.value > root.value and q.value > root.value:
    return LCA_BST(root.right, p, q)  // both in right subtree
  return root  // split point — this is the LCA

This BST version runs in O(h) time and O(h) space (or O(1) space iteratively), compared to O(n) for the general binary tree version.

Time and Space Complexity

Version	Time	Space
General BT	O(n)	O(h) recursion
BST	O(h)	O(h) or O(1) iterative

Applications

• File system: Finding the common parent directory of two files
• Version control: Git merge-base finds the LCA of two commits in the commit graph
• Networking: Finding the common router between two network nodes
• Taxonomy: Finding the most specific common category of two items