Lowest Common Ancestor (LCA) in Binary Trees

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. Defining Common Ancestors

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 can be a descendant of itself).

                 3 (LCA of 5 and 1)
               /   \
             [5]    [1]
             / \    / \
            6   2  0   8
               / \
              7   4

2. Divide and Conquer Recursive Approach

For any subtree rooted at root:

1. If root is null, p, or q, return root.
2. Recursively search the left subtree and right subtree.
3. If both left and right return non-null, root is the split point and therefore the LCA!
4. If only one side returns non-null, pass that non-null node up.

function lowestCommonAncestor(root, p, q) {
  // Base case: Reached null or found p or q
  if (!root || root === p || root === q) {
    return root;
  }

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

  // If p and q are found in different subtrees, root is the LCA!
  if (left !== null && right !== null) {
    return root;
  }

  // Otherwise, return whichever subtree found a target
  return left !== null ? left : right;
}

3. Optimized LCA on a Binary Search Tree (BST)

On a BST, we can use the ordering invariant to find LCA in $O(H)$ time without full tree exploration:

function lowestCommonAncestorBST(root, p, q) {
  while (root) {
    if (p.val < root.val && q.val < root.val) {
      root = root.left; // Both targets in left subtree
    } else if (p.val > root.val && q.val > root.val) {
      root = root.right; // Both targets in right subtree
    } else {
      return root; // Split point found!
    }
  }
  return null;
}

4. Common Mistakes

• Assuming Binary Tree is a BST: Applying the BST comparison optimization on an unsorted generic binary tree fails. Use the general divide-and-conquer approach for generic binary trees.

5. Next Steps

Use divide-and-conquer on tree subproblems. Next, let's explore Heaps and Priority Queues!