235. Lowest Common Ancestor of a BST (Medium)

Problem

Given the root of a Binary Search Tree (BST) and two nodes p and q, return their lowest common ancestor (LCA), the lowest node that has both p and q as descendants (where a node is a descendant of itself).

Example

• root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 → 6
• Same tree, p = 2, q = 4 → 2

LeetCode 235 · Link · Medium

Approach 1: Generic LCA (ignore BST property)

Works for any binary tree. Recurse into both subtrees; the LCA is the node where the paths diverge.

def lowest_common_ancestor(root, p, q):
    if not root or root is p or root is q:
        return root                                   # L1: base cases
    left = lowest_common_ancestor(root.left, p, q)   # L2: search left subtree
    right = lowest_common_ancestor(root.right, p, q) # L3: search right subtree
    if left and right:
        return root                                   # L4: split point found
    return left or right                              # L5: propagate up

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L1 (base check)	O(1)	n	O(n)
L2/L3 (recurse both)	O(1) dispatch	n	O(n) ← dominates (all lines tie)
L4/L5 (return)	O(1)	n	O(n)

Both subtrees are fully explored because this approach doesn’t use the BST ordering invariant to prune.

Complexity

• Time: O(n). Whole tree visited worst case.
• Space: O(h) recursion.

Correct but throws away the BST invariant.

Approach 2: Recursive BST walk

Use the ordering: if both p and q are less than root, go left; if both greater, go right; otherwise root is the split point = the LCA.

def lowest_common_ancestor(root, p, q):
    if p.val < root.val and q.val < root.val:
        return lowest_common_ancestor(root.left, p, q)   # L1: both left
    if p.val > root.val and q.val > root.val:
        return lowest_common_ancestor(root.right, p, q)  # L2: both right
    return root                                           # L3: split point

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L1/L2 (comparison + recurse)	O(1)	one per level	O(h)
L3 (return split)	O(1)	1	O(h) ← bottleneck is path length

We follow exactly one root-to-split path, never branching into both children.

Complexity

• Time: O(h). Follow a single root-to-split path.
• Space: O(h) recursion.

For balanced BSTs, O(log n); for skewed, O(n).

Approach 3: Iterative BST walk (optimal space)

Same logic without recursion.

def lowest_common_ancestor(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left          # L1: move left
        elif p.val > root.val and q.val > root.val:
            root = root.right         # L2: move right
        else:
            return root               # L3: found split
    return None

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L1/L2 (compare + step)	O(1)	one per level	O(h)
L3 (return)	O(1)	1	O(h) ← bottleneck is path length

Complexity

• Time: O(h).
• Space: O(1).

Summary

Approach	Time	Space
Generic LCA	O(n)	O(h)
Recursive BST walk	O(h)	O(h)
Iterative BST walk	O(h)	O(1)

The iterative BST walk is optimal. For generic binary trees (not BSTs), see problem 236, which needs Approach 1.

Test cases

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = [root]
    i = 1
    while q and i < len(vals):
        node = q.pop(0)
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root

def find_node(root, val):
    while root:
        if val == root.val: return root
        root = root.left if val < root.val else root.right
    return None

def lowest_common_ancestor(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root
    return None

def _run_tests():
    t = build_tree([6, 2, 8, 0, 4, 7, 9, None, None, 3, 5])
    assert lowest_common_ancestor(t, find_node(t, 2), find_node(t, 8)).val == 6
    assert lowest_common_ancestor(t, find_node(t, 2), find_node(t, 4)).val == 2
    assert lowest_common_ancestor(t, find_node(t, 0), find_node(t, 5)).val == 2
    # single path: both on right spine
    t2 = build_tree([4, 2, 6, 1, 3, 5, 7])
    assert lowest_common_ancestor(t2, find_node(t2, 5), find_node(t2, 7)).val == 6
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

Related data structures

• Binary Trees & BSTs, BST ordering invariant; iterative walk