Lowest Common Ancestor (LCA)

Concept

The Lowest Common Ancestor (LCA) of two nodes p and q is defined as the lowest node in the tree that has both p and q as descendants. (Note: A node is allowed to be a descendant of itself).

Imagine a family tree. You and your cousin p and q want to find your Lowest Common Ancestor. Your parents are different, but you both share the exact same Grandparent. The Grandparent is the LCA.

This problem appears in two distinct variations:

1. Finding the LCA in a Binary Search Tree (BST) (Easy).
2. Finding the LCA in a standard Binary Tree (Hard).

1. LCA of a Binary Search Tree (BST)

Because a BST is strictly sorted (Left < Root < Right), finding the junction point requires no advanced traversal. We just use math.

If both p and q are smaller than the Root, they are both hiding down the Left branch. The LCA must be down there.
If both p and q are larger than the Root, they are both hiding down the Right branch.
The Splitting Point: If one target is smaller than the Root, and the other target is larger than the Root, the current node is the exact junction point where they diverge! The current node is the LCA.

// Time Complexity: O(log N)
// Space Complexity: O(1)
function lowestCommonAncestorBST(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
    let current = root;

    while (current !== null) {
        if (p.val < current.val && q.val < current.val) {
            // Both are smaller. Move left.
            current = current.left;
        } else if (p.val > current.val && q.val > current.val) {
            // Both are larger. Move right.
            current = current.right;
        } else {
            // The Split occurred! One went left, one went right. 
            // (Or one of them IS the current node). We found the LCA!
            return current;
        }
    }

    return null;
}

2. LCA of a Standard Binary Tree

If the tree is NOT a BST (the numbers are random), we cannot use math to find them.
We must use a Bottom-Up Post-Order Traversal (DFS).

The algorithm asks every node to plunge to the bottom and search for p or q.
If it finds one, it returns true (or returns the Node itself) back up the call stack.
When a Parent node receives a successful “found it” signal from its Left branch, AND a successful signal from its Right branch, that Parent node instantly knows: “I am the exact junction point holding both branches!”

// Time Complexity: O(N) (Might have to search every node)
// Space Complexity: O(N) (Call stack)
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
    // Base Case: We hit the absolute bottom, or we physically found target P or Q!
    // If we found a target, return it upward to tell the parent "I found it down this path!"
    if (root === null || root === p || root === q) {
        return root;
    }

    // Plunge Left and Right
    const leftSignal = lowestCommonAncestor(root.left, p, q);
    const rightSignal = lowestCommonAncestor(root.right, p, q);

    // If BOTH branches returned a node, it means P is down one side, and Q is down the other.
    // The current Root is the exact junction point. Return the Root!
    if (leftSignal !== null && rightSignal !== null) {
        return root;
    }

    // Otherwise, if only ONE branch found a target, we just keep bubbling that 
    // target's signal upwards so the higher parents know we found it.
    // If both are null, we return null.
    return leftSignal !== null ? leftSignal : rightSignal;
}

Interview Questions

Q: In the standard Binary Tree LCA problem, what happens if Node p is 5, and Node q is 10, but 10 is physically the child of 5? (e.g., they are in a straight line, not in two separate branches).
A: This is handled perfectly by the Base Case.
As the recursion plunges down, it hits Node 5 (which is p). The Base Case if (root === p) return root; triggers instantly, returning 5 upward. It never explores the children of 5, so it never actually finds q!
However, the logic remains mathematically sound. Because p was found, and q was not found anywhere else in the rest of the tree, it mathematically proves that q MUST be hiding somewhere underneath p. Therefore, p (5) is technically the lowest common ancestor of itself and its descendant. The algorithm correctly returns 5.

Q: A problem asks for the Lowest Common Ancestor of a tree, but provides you with the physical parent pointers inside the TreeNode class (so each node points backwards to its parent). How does this change the problem?
A: This completely transforms the problem from a Tree problem into an Intersection of Two Linked Lists problem! (LeetCode 160).
Because both p and q point upwards to the Root, you simply treat them as the Heads of two Linked Lists. You use the Two Pointer approach to walk them upwards. When one hits null (the Root), you teleport it to the start of the other node’s path. When they mathematically collide, that collision node is the exact Lowest Common Ancestor!