Lowest Common Ancestor of a Binary Search Tree

Solving tips

Exploit the BST property: comparing a node's value with p.val and q.val tells you which subtree each target is in, so you never explore both sides.
If both targets are less than the node go left, if both greater go right; the first node where they split (or where you land on p or q) is the LCA. O(h) time.
This is tail recursion, so convert it to a simple while loop for O(1) space — the ideal answer here.
Pitfall: don't reach for the generic binary-tree LCA (exploring both children) — it's O(n) and signals you missed the BST hint; and note h can be n on a skewed BST.

Problem

Given the root of a binary search tree and two nodes p and q that are guaranteed to exist in it, return their lowest common ancestor (LCA): the deepest node that has both p and q in its subtree. A node counts as its own ancestor, so if p is an ancestor of q, the answer is p itself. All node values are distinct and the BST ordering property holds everywhere.

Examples

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 → Output: 6 2 is in the left subtree of 6 and 8 in the right, so they split at 6.
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 → Output: 2 4 lives inside 2’s subtree, so 2 is its own ancestor and the LCA.
Input: root = [2,1], p = 2, q = 1 → Output: 2 The root is an ancestor of everything, including itself.

Constraints

2 <= n <= 10^5 nodes; all values distinct; p != q, both present.
Node values fit in a 32-bit signed integer.
The BST property is the whole game: expected time is O(h), where h is the height — you should never need to explore both subtrees.

Think about it first

Hint 1

Standing at any node, comparing its value with `p.val` and `q.val` tells you which subtree each target lives in — without visiting either subtree.

Hint 2

If both targets are smaller than the current node, the LCA is in the left subtree; if both are larger, it's in the right. What's the remaining case?

Hint 3

The first node where `p` and `q` fall on different sides (or where you land exactly on `p` or `q`) is the LCA. That's a single walk down from the root — a loop, no recursion needed.

TL;DR

Walk down from the root until p and q split — O(h) time, O(1) space iteratively.

Approach 1 — Brute force: record both root-to-node paths

Ignore the BST property and treat it as a generic tree: find the path from the root to p, the path to q, then walk the two paths in lockstep — the last node they share is the LCA.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(
        self, root: TreeNode, p: TreeNode, q: TreeNode
    ) -> TreeNode:
        def path_to(target: TreeNode) -> List[TreeNode]:
            path: List[TreeNode] = []
            node = root
            while node:
                path.append(node)
                if node is target:
                    return path
                # still generic-looking, but we must pick a side somehow;
                # a true generic-tree version would DFS both sides
                node = node.left if target.val < node.val else node.right
            return path

        pa, pb = path_to(p), path_to(q)
        lca = root
        for x, y in zip(pa, pb):
            if x is y:
                lca = x
            else:
                break
        return lca

Complexity: O(h) time but O(h) extra space for two stored paths. Nothing here fails the constraints — the waste is conceptual: we materialize two full paths only to compare their prefixes, when the comparison can be done on the fly with zero storage.

Approach 2 — Recursive split search

The insight: at any node, the BST ordering answers “which side is p on? which side is q?” in O(1). If both values are below the node, recurse left; both above, recurse right; otherwise the two targets are on different sides (or one equals the node) — and that node is, by definition, the deepest node containing both. The recursion follows exactly one root-to-LCA path.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(
        self, root: TreeNode, p: TreeNode, q: TreeNode
    ) -> TreeNode:
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        return root

Walkthrough on root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4: at 6, both 2 < 6 and 4 < 6 → go left. At 2, the first condition fails (2 < 2 is false), the second fails (2 > 2 is false) → return 2. Two node visits, and note how “a node is its own ancestor” falls out for free.

Complexity: O(h) time, O(h) recursion stack.

Approach 3 — Iterative walk (O(1) space)

The insight: the recursion above is tail recursion — each call makes at most one recursive call and returns its result unchanged. Any tail recursion converts to a loop, dropping the stack entirely.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(
        self, root: TreeNode, p: TreeNode, q: TreeNode
    ) -> TreeNode:
        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
        return None

Walkthrough on p = 2, q = 8 in the same tree: at 6, 2 < 6 but 8 > 6 — the targets straddle the node, so neither branch is taken and 6 is returned immediately. One iteration.

Complexity: O(h) time, O(1) space — the ideal for this problem.

Common pitfalls

Testing equality with == on values when the problem hands you node references — fine here since values are distinct, but compare node is p when in doubt.
Forgetting that the “split” case includes landing exactly on p or q; writing a separate equality check is redundant but writing the split check as strict inequalities in both directions and looping forever is a bug.
Reaching for the generic binary-tree LCA recursion (explore both children) — correct, but O(n) instead of O(h), and it signals you missed the BST hint.
Assuming h = log n: a skewed BST makes the recursive version O(n) deep, which is exactly why the iterative form is worth showing.

Pattern takeaway

In a BST, comparisons replace search. Whenever a BST problem asks about the relationship between values (predecessor, insertion point, LCA), you can steer a single root-to-leaf walk with O(1) comparisons per step instead of exploring subtrees — and any single-path recursion should convert to an O(1)-space loop.