☕ DSA Java Articles

Topics › Binary Search Trees › Practice Problems

LCA in BST

Medium TUF ID 106 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the root of a binary search tree and the keys p and q of two nodes that are both present in it. Return their lowest common ancestor (LCA): the deepest node that has both of them in its subtree. A node counts as an ancestor of itself, so if p lies inside the subtree of q, the answer is q.

Keys in a BST are distinct, so a key identifies a node uniquely. LeetCode passes node references instead of keys; the code is the same with p.val and q.val. Constraints: up to 10^5 nodes, keys fit in a 32-bit signed integer.

All examples use this tree:

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

Example 1

p = 2, q = 8
answer = 6       // 2 is on the left of 6, 8 on the right

Example 2

p = 2, q = 4
answer = 2       // 4 is inside the subtree of 2, and 2 is its own ancestor

Approach 1: Brute force, the general binary-tree LCA

Intuition. Forget the ordering for a moment; the LCA of a plain binary tree can be found with one recursion. Ask each subtree “do you contain p or q?”. If the current node is p or q, report it. If one key turns up on the left and the other on the right, the current node is where their paths meet, so it is the LCA. If only one side reports something, pass that report upward. Returning a node as soon as it equals p (without looking below it) is safe because both keys are guaranteed to exist: if the other key is not found elsewhere, it must be underneath, and then this node is the answer anyway.

Algorithm.

  1. If root is null or holds p or q, return root.
  2. Recurse into both children.
  3. If both calls return a node, return root. Otherwise return whichever call returned a node (or null).
static TreeNode bruteForce(TreeNode root, int p, int q) {
    if (root == null || root.val == p || root.val == q) return root;
    TreeNode left = bruteForce(root.left, p, q);
    TreeNode right = bruteForce(root.right, p, q);
    if (left != null && right != null) return root;   // p and q were found on different sides
    return left != null ? left : right;
}

Complexity. Time O(n): in the worst case it visits every node, because it never uses the ordering to skip a subtree. Space O(h) for the recursion.

Approach 2: Better, compare the two search paths

Intuition. In a BST the route from the root to a key is forced: compare with the current node and go left or right. The ancestors of p are exactly the nodes on that search path, and the same goes for q. Common ancestors are therefore the common prefix of the two paths, and the lowest common ancestor is the last node of that prefix. The search only touches one root-to-node path per key, so we stop wasting time on irrelevant subtrees.

Algorithm.

  1. Record the search path from the root to p and from the root to q.
  2. Walk both lists from the start while they hold the same node.
  3. The last shared node is the LCA.
static TreeNode better(TreeNode root, int p, int q) {
    List<TreeNode> pathP = searchPath(root, p);
    List<TreeNode> pathQ = searchPath(root, q);
    TreeNode lca = null;
    for (int i = 0; i < pathP.size() && i < pathQ.size(); i++) {
        if (pathP.get(i) != pathQ.get(i)) break;          // same node object, not just same key
        lca = pathP.get(i);
    }
    return lca;
}

static List<TreeNode> searchPath(TreeNode root, int key) {
    List<TreeNode> path = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null) {
        path.add(cur);
        if (key == cur.val) break;
        cur = key < cur.val ? cur.left : cur.right;
    }
    return path;
}

Comparing with != here is deliberate: we want the same node object, not merely the same key.

Complexity. Time O(h) for two searches and one prefix scan. Space O(h) for the two lists. On a balanced tree h ≈ log n; on a chain h = n.

Approach 3: Optimal, find the split point

Intuition. We do not need to store the paths. Walk both searches at the same time from the root. While p and q both want to go left (both smaller than the current key) or both want to go right (both larger), the two paths are still identical, so we move along. The first node where they disagree, meaning one key is on the left and the other on the right, or one of them is the current node, is where the common prefix ends. That node is the LCA.

Why no deeper node can work: below the split node, every node lies entirely in its left subtree or entirely in its right subtree, so it cannot have both p and q under it. And when the current node equals p, any deeper node is below p and cannot contain p itself.

Algorithm.

  1. Start with cur = root.
  2. If both keys are smaller than cur.val, go left. If both are larger, go right.
  3. Otherwise return cur.
static TreeNode optimal(TreeNode root, int p, int q) {
    TreeNode cur = root;
    while (cur != null) {
        if (p < cur.val && q < cur.val) cur = cur.left;          // both keys live in the left subtree
        else if (p > cur.val && q > cur.val) cur = cur.right;    // both keys live in the right subtree
        else return cur;                                          // they split here, or one of them is cur
    }
    return null;
}

Dry run with p = 3, q = 5:

cur p vs cur q vs cur action
6 3 < 6 5 < 6 both left, go to 2
2 3 > 2 5 > 2 both right, go to 4
4 3 < 4 5 > 4 they split, return 4

Complexity. Time O(h): one step down per iteration. Space O(1): a single pointer, no recursion and no lists.

A recursive version of the same logic is just as short, but it costs O(h) stack space for no benefit, since each call makes at most one recursive call and nothing happens after it returns.

Edge cases and pitfalls