Lowest Common Ancestor of a Binary Search Tree

Problem

Given a binary search tree and two of its nodes p and q, return their lowest common ancestor (LCA): the deepest node that has both p and q as descendants. A node counts as a descendant of itself.

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

p = 2, q = 8   →   6
p = 2, q = 4   →   2     (a node can be its own ancestor)
p = 3, q = 5   →   4

All values are unique, and both p and q exist in the tree.
Use the BST ordering: if both values are smaller than the current node, the LCA is in the left subtree; if both are larger, it's in the right subtree. Otherwise, the current node is where their paths split, so it's the LCA.

Hints

Hint 1

Unlike a general binary tree, a BST's sorted structure tells you the LCA's direction directly from a single value comparison at each node — no need to search both subtrees.

Hint 2

If both p and q are smaller than the current node, the LCA must be in the left subtree. If both are larger, it must be in the right subtree.

Hint 3

The first node where p and q 'split' (one is <=, the other is >=) is the LCA — you don't need to go any deeper once that happens.

Solutions

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;
        } else if (p.val > curr.val && q.val > curr.val) {
            curr = curr.right;
        } else {
            return curr; // split point (or one of p/q IS curr) — this is the LCA
        }
    }
    return null;
}

Time: O(h) · Space: O(1) iterative

Problem

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

p = 2, q = 8   →   6
p = 2, q = 4   →   2     (a node can be its own ancestor)
p = 3, q = 5   →   4

All values are unique, and both p and q exist in the tree.
Use the BST ordering: if both values are smaller than the current node, the LCA is in the left subtree; if both are larger, it's in the right subtree. Otherwise, the current node is where their paths split, so it's the LCA.

Hints

Hint 1

Unlike a general binary tree, a BST's sorted structure tells you the LCA's direction directly from a single value comparison at each node — no need to search both subtrees.

Hint 2

If both p and q are smaller than the current node, the LCA must be in the left subtree. If both are larger, it must be in the right subtree.

Hint 3

The first node where p and q 'split' (one is <=, the other is >=) is the LCA — you don't need to go any deeper once that happens.

Solutions

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;
        } else if (p.val > curr.val && q.val > curr.val) {
            curr = curr.right;
        } else {
            return curr; // split point (or one of p/q IS curr) — this is the LCA
        }
    }
    return null;
}

Time: O(h) · Space: O(1) iterative

Problem

Examples

Constraints

Hints

Solutions

Lowest Common Ancestor of a Binary Search Tree

Problem

Examples

Constraints

Hints

Solutions