Lowest Common Ancestor of a Binary Tree

Lowest Common Ancestor of a Binary Tree

What is this problem about?

The Lowest Common Ancestor of a Binary Tree problem gives you a generic binary tree (NOT a Binary Search Tree) and two target nodes, p and q. You must find the deepest node in the tree that has both p and q as descendants. Unlike a BST, the values in this tree are not sorted, so you cannot rely on numerical comparisons to guide your search.

Why is this asked in interviews?

This is arguably the most famous recursion problem in software engineering interviews. It perfectly evaluates a candidate's grasp of Depth-First Search (DFS) and post-order traversal. It tests your ability to bubble up boolean states or node references from the leaves of a tree back up to the root to identify a convergence point.

Algorithmic pattern used

This problem heavily relies on Post-Order Depth-First Search (DFS). The recursive function searches the left and right subtrees.

• Base cases: If the current node is null, return null. If the current node is p or q, return the current node.
• Recursive step: Search the left child and right child.
• Resolution: If both the left and right searches return non-null values, it means p was found in one branch and q in the other. The current node is the convergence point—the LCA! Return it. If only one returns non-null, pass that non-null value upwards.

Example explanation

Imagine a tree: Root 3. Left child 5, Right child 1. We want the LCA of 5 and 1.

• Call DFS on Root 3.
  • Traverse Left to 5. It matches p! Return node 5 upwards.
  • Traverse Right to 1. It matches q! Return node 1 upwards.
• Back at Root 3: The left search returned 5, and the right search returned 1. Since BOTH are non-null, the current node (3) is the split point! Root 3 returns itself. Node 3 is the LCA.

If we wanted the LCA of 5 and a descendant of 5, the search down the other branch would return null, and node 5 would just bubble itself all the way to the top.

Common mistakes candidates make

A frequent mistake is attempting to find paths to p and q from the root, storing them in arrays, and then comparing the arrays to find where they diverge. While this logically works, it takes $O(N)$ extra space and requires multiple passes. The optimal recursive approach finds the answer in a single pass with no extra arrays, utilizing just the recursive call stack.

Interview preparation tip

Memorize the 5-line recursive solution for the Lowest Common Ancestor coding pattern. It is incredibly elegant:

1. Check base cases (null, p, or q).
2. Recurse left.
3. Recurse right.
4. If both left and right are not null, return root.
5. Otherwise, return the one that isn't null. This exact logic serves as a building block for many harder tree-merging problems.