How to Find the Lowest Common Ancestor in a Binary Tree

The Lowest Common Ancestor of two nodes A and B in a tree is the deepest node that has both A and B as descendants. A node can be a descendant of itself, so if A is an ancestor of B then A itself is the LCA.

If the current node is NULL, return NULL because we have gone past a leaf without finding anything. If the current node equals node A or node B, return the current node immediately. This signals to the parent that one of the target nodes has been found here.

Recursively call the LCA function on the left subtree and store the result. Recursively call the LCA function on the right subtree and store the result. Both calls independently search for node A and node B.

After both recursive calls return, examine what came back. If both the left result and the right result are non-NULL, it means one target node was found in the left subtree and the other was found in the right subtree. The current node is therefore the LCA. Return the current node.

If only the left result is non-NULL, it means both target nodes are somewhere in the left subtree. Return the left result upward. If only the right result is non-NULL, both nodes are in the right subtree. Return the right result upward. The LCA has already been identified deeper in that subtree.

If both the left and right results are NULL, neither target node exists in this subtree. Return NULL to the parent to indicate nothing was found here.

The recursion naturally bubbles up the answer. Once the LCA is found at some node because both left and right return non-NULL, it gets returned all the way up to the root without being overwritten. The algorithm never explicitly stores parent pointers or paths, yet finds the correct answer in a single pass.