23. Lowest Common Ancestor of a Binary Tree

Difficulty:MediumPattern:Tree Post-Order DFSTime:O(n)Space:O(h)

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q.

How It Works & Algorithmic Design

Solves using Recursive DFS Post-Order Traversal:

Base Cases: If root === null or root === p or root === q, return root.
Recurse:
- left = lowestCommonAncestor(root.left, p, q).
- right = lowestCommonAncestor(root.right, p, q).
LCA Decision:
- If both left !== null and right !== null, p and q exist in separate subtrees of root $\to$ root is the LCA!
- If only one side is non-null, return that non-null side (left || right).

Why This Approach Works Best

Post-order traversal evaluates child subtrees first, correctly bubbling up common ancestor points in $O(n)$ time.

Example Walkthrough

Input Tree: root = [3, 5, 1, 6, 2, 0, 8], p = 5, q = 1

Target nodes 5 and 1.

LCA Calculation: Left subtree contains 5, Right subtree contains 1 -> Ancestor node is 3.

Root 3 splits target nodes.

Output: 3

Lowest common ancestor.

Answer: Lowest Common Ancestor DFS implementation

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left || right;
}

💡 Bubble up found target nodes using post-order DFS to identify meeting ancestor.

Key Takeaways

If both left and right return non-null, current root is the LCA.
If only one side returns non-null, both nodes lie in that subtree.
Runs in linear $O(n)$ time.