LeetCode Lowest Common Ancestor of a BST

LeetCode 235 — Lowest Common Ancestor of a Binary Search Tree — is the gentler twin of LeetCode 236. On a generic binary tree, finding the LCA requires a careful post-order trick. On a BST, the ordering hands you the answer almost for free: the LCA is the first node whose value sits between the two targets.

The Problem

Given the root of a BST and two nodes p and q (guaranteed to exist), return their lowest common ancestor — the deepest node that has both p and q as descendants. By convention, a node is a descendant of itself, so if p is an ancestor of q, the answer is p.

Brute Force

Forget about the BST property and treat it as a generic binary tree. Recurse left and right; if both sides return non-null, the current node is the LCA.

def lowestCommonAncestor(root, p, q):
    if not root or root is p or root is q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    return left or right

This is O(n) and works, but it wastes the structure. An interviewer will ask if you can do better.

Optimal Solution

Use the BST property. Walk from the root:

• If both p and q are less than the current node, the LCA is in the left subtree.
• If both are greater, it is in the right subtree.
• Otherwise the current node splits them — it is the LCA.

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

Iterative, O(h) time, O(1) space. The recursive version is identical in structure but uses O(h) stack.

Walk Through an Example

Take the BST [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5] with p = 2 and q = 8.

• Start at 6. p.val = 2 < 6 and q.val = 8 > 6. They split here. Return 6.

Now try p = 2, q = 4.

• Start at 6. Both targets are less than 6. Go left.
• At 2. Now p equals the current node. Since p.val is not strictly less and not strictly greater, the condition falls through to return node. Answer: 2.

The “node is a descendant of itself” rule is exactly what makes the early termination clean.

Edge Cases

• One node is an ancestor of the other — handled, because the comparison falls through when one value equals the current node.
• p and q are the same node — return that node.
• A skewed BST that is essentially a sorted linked list — still O(h), where h equals n. Worth flagging in interview if you suspect adversarial input.
• The tree contains duplicates — the standard problem forbids this; if asked, you must define BST strictness first.

Complexity Analysis

Time is O(h) where h is tree height. Balanced BST gives O(log n), skewed BST gives O(n). Space is O(1) for the iterative version and O(h) for the recursive one. The brute-force generic-tree solution remains O(n) time and O(n) space.

If the comparison of “O(h) vs O(n)” feels fuzzy, the Big-O notation post covers how to talk about height-bound complexities cleanly.

How to Explain It in an Interview

State the property first: “In a BST, the LCA of p and q is the first node on the root-to-leaf path whose value lies between them, inclusive.” Then derive the three cases. Mention you could fall back to the generic LCA approach if the BST invariant were broken. Close with the space trade — recursive is shorter, iterative wins on stack frames.

Related Problems

• LeetCode 236 — Lowest Common Ancestor of a Binary Tree (the generic version)
• LeetCode 1644 — LCA when nodes may not exist
• LeetCode 1650 — LCA with parent pointers
• LeetCode 98 — Validate Binary Search Tree

For deeper coverage of traversals that LCA-style problems lean on, see Binary Tree Traversals.

Wrap up

LCA on a BST is the rare problem where the optimal solution is shorter than the brute force and runs in less memory. The lesson is to always ask: what invariant does the data structure give me? Here, sorted order collapses an entire DFS into a guided walk. Lock in the three-case template and this problem becomes a freebie.