Leetcode 236. Lowest Common Ancestor of a Binary Tree

Let's understand what we're being asked to do. We have a binary tree and two nodes p and q somewhere in that tree. We need to find their lowest common ancestor (LCA) - the deepest node that has both p and q as descendants.

Important: a node can be a descendant of itself. This means if p is an ancestor of q, then p itself is the LCA!

Let's trace through an example tree:

       3
      / \
     5   1
    / \ / \
   6  2 0  8
     / \
    7   4

If p=5 and q=1, the LCA is 3 (the root is the lowest node that has both as descendants).

If p=5 and q=4, the LCA is 5 (node 5 is an ancestor of node 4, and a node can be its own descendant).

Key constraints: Both p and q are guaranteed to exist in the tree, all node values are unique, and the tree can have up to 200,000 nodes.

Edge cases to consider: What if p or q is the root? What if one node is a direct ancestor of the other? What if the tree has only two nodes?

The LCA is the split point where the paths from root to p and root to q diverge.

If we're at a node and p is in the left subtree while q is in the right subtree (or vice versa), then this current node must be the LCA. If both are in the same subtree, the LCA must be deeper in that subtree.

This observation means we can solve this with a single tree traversal. At each node, we ask: 'Are p and q in different subtrees of this node?'

If yes, we've found the LCA. If no, we recurse into whichever subtree contains both nodes. We don't need to store paths or do multiple passes!

Think of the tree as a family tree. The LCA is the most recent common ancestor.

Imagine tracing the lineage from each person back to their ancestors. The LCA is the first ancestor they share when going backwards. If person A is an ancestor of person B, then A is their own LCA (since A is in the lineage from A to root, and also in the lineage from B to root).

We can find this by exploring the tree and checking: 'At this ancestor, do the two people branch off in different directions, or are they both down the same branch?'

Use recursive DFS to traverse the tree. At each node, recursively search for p and q in the left and right subtrees. If the current node is p or q, return it. If both left and right recursive calls return non-null values, it means p and q are in different subtrees, so the current node is the LCA. If only one side returns non-null, propagate that result upward (both nodes are in that subtree). This finds the LCA in a single traversal.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def lowest_common_ancestor(root, p, q):
    """
    Find the lowest common ancestor of two nodes in a binary tree.
    Uses recursive DFS to search for p and q in subtrees.
    """
    # Base case: if root is None or root is one of the target nodes
    if root is None:
        return None
    
    if root.val == p or root.val == q:
        return root
    
    # Recursively search in left and right subtrees
    left_result = lowest_common_ancestor(root.left, p, q)
    right_result = lowest_common_ancestor(root.right, p, q)
    
    # If both left and right return non-null, current node is LCA
    if left_result is not None and right_result is not None:
        return root
    
    # Otherwise, return the non-null result (both nodes in same subtree)
    if left_result is not None:
        return left_result
    else:
        return right_result

• Recursive post-order traversal for LCA: The LCA problem is solved elegantly using post-order traversal (left-right-root) because you need information from both subtrees before making a decision at the current node - if both subtrees return non-null, the current node is the LCA.
• Null propagation as signal mechanism: Use null returns to propagate search results up the tree - return the found node (p or q) when discovered, return null when neither is found, and this creates a natural signaling system where the first node receiving two non-null children is the answer.
• Self-ancestor handling: A critical insight is that a node can be its own ancestor - if you find p and q is in p's subtree (or vice versa), then p itself is the LCA, which the algorithm handles naturally by returning p immediately when found.
• Single-pass efficiency through bottom-up processing: This solution achieves O(n) time with O(h) space by visiting each node exactly once and making the LCA decision during the return phase, avoiding the need for separate path-finding or parent-pointer approaches that would require multiple passes.
• Common mistake - premature decision making: A frequent error is trying to determine the LCA while traversing down (top-down), but you lack the information needed until you've explored both subtrees - always gather information from children before processing the parent in tree ancestry problems.
• Pattern extension to organizational hierarchies: This LCA algorithm directly applies to finding common managers in org charts, nearest common ancestors in file systems, or merge points in version control - any hierarchical structure where you need to find the closest common parent of two entities.