Finding the Lowest Common Ancestor in a Binary Tree

Welcome back! In our previous lessons, we've explored two fundamental recursive patterns for binary trees: bubbling results up the tree (post-order, like calculating tree height) and passing constraints down the tree (pre-order, like validating a BST).

Today, we'll strengthen our understanding of the "bubble-up" pattern by applying it to another classic interview problem: finding the Lowest Common Ancestor (LCA) of two nodes. This problem requires a clever use of recursive return values to signal where the target nodes are found. Mastering this will not only add another essential algorithm to your toolkit but also deepen your intuition for how recursive functions can communicate information up the call stack.

What is the Lowest Common Ancestor?

The Lowest Common Ancestor (LCA) of two nodes, p and q, in a binary tree is the lowest (i.e., deepest) node that has both p and q as descendants. A key rule here, which often trips people up, is that a node is considered a descendant of itself.

This rule gives rise to two main scenarios, which are visualized perfectly in the image below.

1. Standard Case: p and q are in different subtrees of their LCA. The LCA is the "junction point" where the paths from the root to p and q diverge.
2. Edge Case: One node is an ancestor of the other. For instance, if p is an ancestor of q, then p is their LCA.

With this definition in mind, our task is to design an algorithm that can efficiently find this node.

A Recursive Approach: Thinking from a Single Node's Perspective

A brute-force method might involve finding the path from the root to p, finding the path from the root to q, and then comparing these paths to find the last common node. This works, but it requires extra space to store the paths. As you've seen, recursion often provides a more elegant solution for tree problems by avoiding extra storage.

The key to the recursive solution is to define what our function should "report back" from any given subtree. Let's define a recursive function find(node, p, q) that traverses the tree. For any given node, what information can it provide to its parent? It can tell its parent one of three things about the subtree it's rooting:

1. "I found p in my subtree."
2. "I found q in my subtree."
3. "I found neither p nor q in my subtree."

How does this help? Imagine you're at a currentNode. You ask your left child to find(p, q) and your right child to find(p, q).

• If the left child reports finding p and the right child reports finding q, then currentNode must be the LCA! It's the first node to "see" p and q in separate subtrees.
• If the left child reports finding p (or q), but the right child reports finding nothing, then the LCA must be in the left subtree. The currentNode isn't the LCA, so it should just pass the report from its left child up to its own parent.
• If the current node itself is p or q, it has found one of the targets. It can immediately report this back to its parent.

The following video from Back To Back SWE provides an excellent explanation of this "single node policy," which is the core intuition for solving this problem recursively.

The Algorithm in Detail

The intuition from the video translates into a concise, three-part recursive algorithm: base cases, recursive exploration, and decision logic. The following resource from AlgoMonster breaks this down very clearly.

To summarize the logic from the reading:

1. Base Cases:

   • If the current node is null, we've reached the end of a branch. Return null.
   • If the current node is p or q, we've found one of our targets. Return the current node.

2. Recursive Step:

   • Call the function recursively on the left child: leftResult = lowestCommonAncestor(root.left, p, q).
   • Call the function recursively on the right child: rightResult = lowestCommonAncestor(root.right, p, q).

3. Decision Logic:

   • If leftResult and rightResult are both non-null, the current root is the LCA. Return root.
   • Otherwise, the LCA (or one of the target nodes) is in one of the subtrees. Return whichever of leftResult or rightResult is not null. If both are null, this will correctly return null.

This is a post-order traversal pattern: the decision at a node is made after the recursive calls to its children have returned.

Visualizing the Recursive Calls

Seeing the algorithm in action helps connect all the pieces. The next video provides a step-by-step visual trace of the recursive calls and what they return.

TypeScript Implementation

Now, let's translate this logic into a TypeScript function. The code is a direct implementation of the three-step process we've discussed.

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

function lowestCommonAncestor(
    root: TreeNode | null, 
    p: TreeNode | null, 
    q: TreeNode | null
): TreeNode | null {
    // 1. Base Cases: If root is null, or we found p or q.
    if (!root || root === p || root === q) {
        return root;
    }

    // 2. Recursive Step: Search in left and right subtrees.
    const leftResult = lowestCommonAncestor(root.left, p, q);
    const rightResult = lowestCommonAncestor(root.right, p, q);

    // 3. Decision Logic: Combine the results.
    
    // If both children returned a non-null node, p and q are in different
    // subtrees. This means the current root is their LCA.
    if (leftResult && rightResult) {
        return root;
    }
    
    // Otherwise, the LCA must be in whichever subtree returned a non-null
    // result. We propagate that result upwards. If both were null, this
    // correctly returns null.
    return leftResult || rightResult;
};

This algorithm visits each node in the tree once, so its time complexity is $O(N)$, where $N$ is the number of nodes. The space complexity is determined by the maximum depth of the recursion stack, which is equal to the height of the tree, $O(H)$. For a balanced tree, this is $O(\log N)$, but for a skewed tree, it can be $O(N)$ in the worst case.

Conclusion

In this lesson, we dissected the Lowest Common Ancestor problem and developed an elegant recursive solution. This algorithm is a prime example of a post-order traversal where information is "bubbled up" the call stack to solve a global problem.

Key Takeaways:

• LCA Definition: The LCA is the deepest node that is an ancestor to both target nodes. Remember that a node can be a descendant of itself.
• Recursive Strategy: The solution relies on a recursive function that reports what it finds in its subtree: p, q, or null.
• The "Split Point" is the LCA: A node is the LCA if and only if the recursive calls on its left and right children both return non-null values. This means the targets p and q are in different subtrees, and the current node is their first meeting point.
• Propagating Results: If only one child returns a non-null value, it means both targets are in that one subtree. The current node simply passes that result up to its parent.

In our next lesson, we'll shift our focus from general tree traversal algorithms to a specialized tree-based data structure: the binary min-heap. Heaps are fundamental for implementing priority queues and solving a wide range of problems involving ordering and selection, such as finding the "top K" elements in a dataset.