Lowest Common Ancestor of a Binary Search Tree

MEDIUM✓ CHIP-TIMEDLC #235 — FULL STATEMENT ↗

The drill: Given two nodes somewhere in a binary search tree, find the deepest node that has both of them as descendants — a node counts as its own descendant.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A binary search tree arrives along with two of its nodes, and the task is to find the deepest node in the tree that counts both of them among its descendants.

A node is considered its own descendant, so if one of the two target nodes happens to be an ancestor of the other, that target node itself is the answer.

Both target nodes are guaranteed to exist somewhere in the tree, and the tree's search-tree ordering — everything smaller to the left, everything larger to the right — holds throughout.

EX 01

root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5] · p = [2] · q = [8]

→ [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]

TARGETS SPLIT AT THE ROOT

EX 02

root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5] · p = [2] · q = [4]

→ [2, 0, 4, null, null, 3, 5]

ONE TARGET IS AN ANCESTOR OF THE OTHER

EX 03

root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5] · p = [0] · q = [3]

→ [2, 0, 4, null, null, 3, 5]

BOTH TARGETS SIT DEEP IN THE SAME LEFT BRANCH

both target nodes exist in the tree and are distinct
the tree can hold anywhere from a couple of nodes to a few thousand
all values in the tree are unique and follow standard BST ordering
a node counts as its own descendant when checking ancestry

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Ignoring the search-tree ordering entirely still gives a correct answer: search both subtrees for each target and combine what comes back. It just never uses the one fact this tree offers for free.

HINT 2 THE STRUCTURE

In a BST, a node's value alone tells you which side any other value lives on. If both targets are smaller than the current node, the answer can't be here — it's entirely in the left subtree, and symmetrically for the right.

HINT 3 ONE STEP FROM THE ANSWER

Walk down from the root comparing both target values against the current node's value: same-side, step that way; split (or a match), stop — that node is the answer.

COACH'S BOARD — THE PATTERN, STEP BY STEP

FOLLOW THE ORDERINGPATTERN · FOLLOW THE ORDERINGroot = [6,2,8,0,4,7,9,null,null,3,5] · p = 3 · q = 5

STEP 1

Find the deepest node that's an ancestor of both 3 and 5. The BST ordering tells us which side to walk without ever searching — start at the root, 6.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/lowest-common-ancestor-of-a-binary-search-tree.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def lowestCommonAncestor(self, root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode":
        curr = root
        while curr:
            if p.val < curr.val and q.val < curr.val:
                curr = curr.left
            elif p.val > curr.val and q.val > curr.val:
                curr = curr.right
            else:
                return curr
        return None

TIME O(H)SPACE O(1)PYTHON · RACE PACE · 11 LN

class Solution:
    def lowestCommonAncestor(self, root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode":
        if root is None or root.val == p.val or root.val == q.val:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left if left else right

TIME O(N)SPACE O(H)PYTHON · TRAINING PACE · 9 LN

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;
            } else if (p.val > curr.val && q.val > curr.val) {
                curr = curr.right;
            } else {
                return curr;
            }
        }
        return null;
    }
}

TIME O(H)SPACE O(1)JAVA · RACE PACE · 15 LN

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root.val == p.val || root.val == q.val) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }
}

TIME O(N)SPACE O(H)JAVA · TRAINING PACE · 13 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED