Find the lowest common ancestor of two nodes in a binary tree.

What the answer has to establish

The lowest common ancestor of p and q is the deepest node that has both of them somewhere in its subtree, where a node counts as its own descendant. That last clause is the whole reason the problem has an edge case: if p sits on the path from the root to q, then p itself is the answer, and a solution that only looks for a node with one target on each side will walk straight past it.

Before writing code, settle two things with the interviewer. Are both nodes guaranteed present in the tree, and are you matching on reference identity or on value? The clean four-line solution silently assumes both are present, and a tree with duplicate values makes value matching ambiguous. Asking is worth marks on its own, because it is the difference between reciting a solution and understanding its preconditions.

The post-order recursion

Assume both nodes are present and you compare by identity. Then the entire algorithm is one bottom-up traversal.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // A null subtree contains neither target; hitting p or q means "found here".
    if (root == null || root == p || root == q) {
        return root;
    }

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    // Both sides reported a target, so the paths diverge exactly here.
    if (left != null && right != null) {
        return root;
    }

    // Otherwise pass upwards whichever side found something, or null.
    return left != null ? left : right;
}

The reason this works is that the return value carries a precise meaning, and the meaning is what you should say out loud: the call on a subtree returns the LCA if both targets are inside that subtree, returns whichever single target it contains if only one is, and returns null if it contains neither. Two non-null children means the subtree holds both targets and diverges here; one non-null child means only one target lives below, so the caller needs its identity to keep searching. Nothing else can occur, so checking the branches against that invariant is the whole proof.

The ancestor case is handled by the base case rather than by extra logic. If root == p, the function returns p immediately without descending, so it never discovers that q lies below. That is safe only because both nodes are guaranteed present: the sibling call must return null, so p propagates all the way up and becomes the answer. This is exactly where the guarantee is load-bearing, and it is the detail strong candidates volunteer.

When the guarantee is dropped

If q might be absent, the four-line version returns p and confidently reports an ancestor of a node that does not exist. Fixing it means separating "I found a target" from "I found the answer", so the traversal cannot terminate early.

private TreeNode answer;
private int found;

public TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    answer = null;
    found = 0;
    search(root, p, q);
    return found == 2 ? answer : null;   // only trust the answer if both exist
}

// Returns whether the subtree rooted at node contains p or q.
private boolean search(TreeNode node, TreeNode p, TreeNode q) {
    if (node == null) {
        return false;
    }
    boolean inLeft = search(node.left, p, q);      // full traversal, no short circuit
    boolean inRight = search(node.right, p, q);
    boolean isTarget = (node == p || node == q);

    if (isTarget) {
        found++;
    }
    if ((inLeft && inRight) || (isTarget && (inLeft || inRight))) {
        if (answer == null) {
            answer = node;   // post-order, so the deepest qualifying node is set first
        }
    }
    return inLeft || inRight || isTarget;
}

What a BST changes

In a binary search tree you no longer need to visit both children, because the values tell you where the targets are. Starting at the root, if both target values are smaller than the current node the answer is entirely in the left subtree; if both are larger, it is in the right subtree. The first node where that fails is the split point, and it is the LCA.

public TreeNode lcaBst(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode node = root;
    while (node != null) {
        if (p.val < node.val && q.val < node.val) {
            node = node.left;
        } else if (p.val > node.val && q.val > node.val) {
            node = node.right;
        } else {
            return node;   // split point, or node is p or q itself
        }
    }
    return null;
}

That loop is iterative, so it uses O(1) extra space and runs in O(h) time, where h is the height. On a balanced BST that is O(log n) rather than O(n), and the ancestor case needs no special handling because a node equal to one target immediately falls into the else.

What parent pointers change

Given a parent reference on each node, this stops being a tree problem. The upward paths from p and from q necessarily merge at the LCA, so it is the intersection of two singly linked lists sharing a tail. Compute both depths, advance the deeper node until the depths match, then step both upwards until the references are equal. That is O(h) time and O(1) space, and it never touches the root. Storing every ancestor of p in a hash set and walking up from q also works, but it spends O(h) space on a problem that has an O(1) solution.

Complexity

The general solution visits every node once with constant work per node, so it is O(n) time and O(h) stack space, which is O(log n) balanced and O(n) on a degenerate chain that can overflow the stack. The BST and parent-pointer variants are O(h) time because they exploit structure the general solution has no way to use.

The identity of the return value is the whole algorithm: each call answers "the LCA if both targets are below me, otherwise whichever one is". Say that before you write the code, and the base cases stop looking arbitrary.