Lowest Common Ancestor of a Binary Tree II

Lowest Common Ancestor of a Binary Tree II

What is this problem about?

This is a trickier variation of the standard LCA problem. You are given a binary tree and two nodes, p and q. You must find their Lowest Common Ancestor. The catch? It is NOT guaranteed that p or q actually exist in the tree! If either node is completely missing from the tree, you must return null.

Why is this asked in interviews?

Interviewers ask this variation to catch candidates who blindly memorize the standard LCA template. In the standard LCA problem, if you find p, you immediately return p without searching its subtrees for q (because if q is under p, p is the LCA). But here, if you return early, you might never verify if q actually exists in the tree! This tests edge-case awareness and thorough graph traversal.

Algorithmic pattern used

This problem still uses Depth-First Search (DFS), but with a slight structural modification. You must ensure the entire tree (or at least enough of it to find both nodes) is fully traversed. You can use two boolean flags (e.g., foundP and foundQ) that get set to true when the nodes are encountered during the DFS. The LCA is calculated exactly like the standard problem, but before returning the final answer, you verify that both flags are true.

Example explanation

Tree: Root 3, Left 5, Right 1. Find LCA of 5 and 99 (99 does not exist).

• Using standard LCA: DFS hits 5, returns 5. DFS hits 1, returns null. Root 3 sees left=5, right=null, and bubbles up 5. It incorrectly reports 5 as the LCA!
• Using LCA II approach: We traverse deeply.
  • Hit 5. Set foundP = true. Continue traversing its children to look for 99. Returns 5.
  • Hit 1. Doesn't match. Returns null.
  • Root 3 bubbles up 5.
  • Before returning the final result, we check our flags. foundP is true, but foundQ is false! We return null.

Common mistakes candidates make

The fatal flaw is using the standard $O(N)$ short-circuiting LCA template. If you return immediately upon finding p, you skip searching the rest of that branch. If q happens to be missing entirely, your algorithm won't know the difference between "q is under p" and "q doesn't exist". You must traverse the subtrees of a matched node if the other target hasn't been found yet.

Interview preparation tip

When facing the Lowest Common Ancestor II interview question, the safest approach is to create a DFS function that returns a boolean or an integer count of how many targets were found in a subtree. Alternatively, use global/instance boolean flags and a slightly modified post-order traversal that forces execution on both left and right children before evaluating the current node.