Lowest Common Ancestor

The lowest common ancestor (LCA) of two nodes p and q in a tree is the deepest node that has both p and q as descendants (where a node is considered a descendant of itself). LCA appears in version-control merge bases, phylogenetic trees, and many coding interviews.

LCA in a General Binary Tree — O(n)

Without ordering guarantees we must search the entire tree. The insight: if the current node is p or q, it might be the LCA. If p is found in the left subtree and q in the right (or vice versa), the current node is the LCA.

class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

function lowestCommonAncestor(root, p, q) {
  if (!root) return null;
  // If root is one of the targets, it must be the LCA
  if (root === p || root === q) return root;

  const left  = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  // p and q are in different subtrees — current root is LCA
  if (left && right) return root;
  // Both in same subtree — bubble up the found node
  return left ?? right;
}

This runs in O(n) time and O(h) space (call stack). Every node is visited at most once. The function returns the LCA node if found, or null if neither target is in the subtree.

Tracing an Example

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

lowestCommonAncestor(root, node5, node4):

• At node 5: it equals p, return node 5 immediately.
• At node 3: left returned node 5, right returned null (node 4 is under node 5, so the right subtree of 3 finds nothing).
• Result: node 5 — correct, because node 5 is an ancestor of node 4.

LCA in a BST — O(h)

A BST’s ordering eliminates the need to search both subtrees:

• If both p and q are less than the current node, the LCA is in the left subtree.
• If both are greater, the LCA is in the right subtree.
• Otherwise the current node is the split point — it is the LCA.

function lcaBST(root, p, q) {
  let node = root;
  while (node) {
    if (p.val < node.val && q.val < node.val) {
      node = node.left;
    } else if (p.val > node.val && q.val > node.val) {
      node = node.right;
    } else {
      return node;  // split point is the LCA
    }
  }
  return null;
}

This iterative version uses O(1) space and O(h) time — O(log n) for a balanced BST.

Complexity Comparison

Up Next

Serialization encodes a tree into a string so it can be transmitted or stored and then reconstructed exactly — a classic interview problem that ties together traversal and tree construction.