Find LCA of 2 nodes in a BST

The problem, simply

You get a binary search tree (BST) and two numbers p and q that are both in it. Find their lowest common ancestor (LCA): the deepest spot that has both p and q somewhere below it. A spot counts as being below itself, so if p sits above q, the answer is p.

A story to remember it

Picture it

Examples

Way 1: the simple way

Forget the sorting and solve it for any binary tree. Ask each side: "do you contain p or q?"

1. If the spot is null, return null.
2. If the spot is p or q, return it.
3. Ask the left side and the right side.
4. If both sides found something, this spot is where they split. Return it.
5. Otherwise return whichever side found something.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;   // one on each side
        return left != null ? left : right;               // pass up what was found
    }
}

How long it takes: it may visit every spot, O(n). Extra room: the recursion depth, O(h). Correct, but it ignores the signposts.

Way 2: the clever way

Walk down with one finger, curr, starting at the top.

1. If both p and q are smaller than curr, both live on the left. Go left.
2. If both are bigger, both live on the right. Go right.
3. Otherwise they split here, or one of them is curr. Return curr.

Why it is the lowest: at the split, one number is on the left side and the other on the right (or is curr itself). No spot below curr can have both, because the two sides never meet again.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode curr = root;
        while (curr != null) {
            if (p.val < curr.val && q.val < curr.val) {
                curr = curr.left;            // both live on the left
            } else if (p.val > curr.val && q.val > curr.val) {
                curr = curr.right;           // both live on the right
            } else {
                return curr;                 // they split here
            }
        }
        return null;                         // only if p or q is missing
    }
}

How long it takes: one road down, O(h). Extra room: one finger, O(1).

Watch out for

• If p or q might be missing from the tree, the walk still returns a spot. Check both are really there (two searches) before trusting the answer.
• Comparing node objects in Way 2. Compare values, since the walk only needs the numbers.
• Using Way 2 on a tree that is not a BST. It only works because of the ordering.

What interviewers ask next

• LCA in a plain binary tree (LeetCode 236). Use Way 1. It is the general tool.
• Distance between p and q in a BST. Find the split spot, then add the number of steps from it down to p and down to q.
• Many LCA questions on a fixed tree. Precompute "jump 1, 2, 4, 8 ... steps up" tables (binary lifting) for O(log n) per question.
• What if nodes have parent pointers? Walk up from both, like finding where two linked lists meet.

Remember this

Grown-up words: the last corner the friends shared is the lowest common ancestor, the corner where they split is the split point of the two search paths, and "a spot is below itself" means a node is a descendant of itself.