A billing org stores customer IDs in a BST so range lookups stay cheap. Fraud ops needs the lowest node that still covers two flagged accounts — attach the freeze once, as deep as possible. The first patch treated the catalog as an unordered binary tree: search left, search right, combine. That is correct when there is no order. On a BST the split is already sitting on the current node.

The lowest common ancestor is the deepest node that still has both keys under it — including itself. The same order Validate BST carries as bounds on a walk is why that split is unique. Here we only care about following it, not about proving the tree is valid.

The problem

Given the root of a BST and two nodes p and q that exist in the tree, return their lowest common ancestor. A node may be an ancestor of itself. Empty tree and missing keys are out of contract — the prompt promises both nodes are present.

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Sample tree and the three shapes that matter: a true split, a node that is an ancestor of the other, and a split one level down.

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

p=2, q=8  →  6     split at the root
p=2, q=4  →  2     2 is an ancestor of 4
p=3, q=5  →  4     split under 2

Note: Do not start a pair of subtree searches. That is LCA of a Binary Tree — a different problem, because there is no order to follow.

Two paths, last shared node

Walk from the root to p, then from the root to q. The last shared node is the LCA — correct, extra lists, and it ignores BST order.

TreeNode lowestCommonAncestorBrute(TreeNode root, TreeNode p, TreeNode q) {
    List<TreeNode> pathP = new ArrayList<>();
    List<TreeNode> pathQ = new ArrayList<>();
    pathTo(root, p, pathP);
    pathTo(root, q, pathQ);
    TreeNode lca = null;
    int n = Math.min(pathP.size(), pathQ.size());
    for (int i = 0; i < n && pathP.get(i) == pathQ.get(i); i++) {
        lca = pathP.get(i);
    }
    return lca;
}

boolean pathTo(TreeNode node, TreeNode target, List<TreeNode> path) {
    if (node == null) {
        return false;
    }
    path.add(node);
    if (node == target) {
        return true;
    }
    if (pathTo(node.left, target, path) || pathTo(node.right, target, path)) {
        return true;
    }
    path.remove(path.size() - 1);
    return false;
}

At a handful of nodes this is fine. On a tall spine you built two O(h) lists and still walked like the keys were unordered. The intended walk never records a path.

One walk: follow the split

Start at the root. While the current node is not the answer:

  • Both p and q smaller than node.val — the split is still in the left child. Step left.
  • Both larger — step right.
  • Otherwise the keys split here, or one of them is this node. Return it.

That third case is the LCA. You do not search the other child. A while loop is nicer at the board than a recursive restatement of the same three branches.

p=2, q=8
node=6   2 < 6 < 8     split → 6

p=2, q=4
node=6   both < 6      left
node=2   2 == p        equal → 2

p=3, q=5
node=6   both < 6      left
node=2   both > 2      right
node=4   3 < 4 < 5     split → 4

The Java is that walk:

TreeNode lowestCommonAncestor(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;
        }
    }
    return null;
}

Time is O(h) — one descent, h being height. Space is O(1) for the iterative walk. Recursion is the same three branches and O(h) frames; a spine of a million IDs is a million frames. Return null only if the tree was empty. Under the “both exist” contract you never need it on a non-empty root.

Note: Compare values, not object identity, for the left/right decision. Identity still matters for “this node is p” — that case falls out of the split branch when one key equals node.val.

What interviewers usually poke next

  • LCA of a Binary Tree. No search-tree order, so you do search both subtrees and combine. Different problem; do not start that recursion here. Future writeup: /interview/trees/medium/lowest-common-ancestor-of-a-binary-tree/.
  • Missing p or q. The prompt promised both exist. If they might be absent, say the contract changed — you would have to prove presence, not assume the split.
  • A node is an ancestor of itself. p=2, q=4 returning 2 is the test. If they want a strict parent, that is a different return.
  • Recursive one-liner. Same three branches, return lowestCommonAncestor(node.left, p, q) (or right). Prefer the loop unless they ask for recursion.
  • Why not both children anyway? It still works and pays O(n). They gave you a BST so you would not.

You are done with this problem when you can point at the split on the drawing, return the node that is p when q sits under it, and refuse to start a pair of subtree searches.