Lowest Common Ancestor of a Binary Search Tree

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 is 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 every node, 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 ordering property lets you solve this in O(h) time, where h is the height, without exploring both subtrees.

Think about it first

TL;DR

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

The examples below use this tree, root = [6,2,8,0,4,7,9,null,null,3,5]:

graph TD
    6 --> 2
    6 --> 8
    2 --> 0
    2 --> 4
    4 --> 3
    4 --> 5
    8 --> 7
    8 --> 9

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

Ignore the BST property and treat the tree as generic: 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

def lowestCommonAncestor(
    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 and O(h) extra space for the two stored paths. This passes the constraints, but it is wasteful: it materializes two full paths only to compare their prefixes, when the comparison can be done on the fly with no storage.

Approach 2 — Recursive split search

At any node, the BST ordering tells you in O(1) which side p and q each fall on. If both values are below the node, recurse left; if both are above, recurse right; otherwise the two targets are on different sides (or one equals the node), and that node is 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

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

Walkthrough on p = 2, q = 4: at 6, both 2 < 6 and 4 < 6, so go left. At 2, the first condition fails (2 < 2 is false) and the second fails (2 > 2 is false), so return 2. Two node visits, and the “a node is its own ancestor” case is handled without a special check.

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

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

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 call stack entirely.

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

def lowestCommonAncestor(
    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: at 6, 2 < 6 but 8 > 6, so the targets straddle the node. Neither branch is taken and 6 is returned immediately. One iteration.

Complexity: O(h) time, O(1) space, which is optimal 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 that explores both children: it is correct, but O(n) instead of O(h), and it ignores the BST property.
• Assuming h = log n. A skewed BST makes the recursive version O(n) deep, which is why the iterative form matters.

Pattern takeaway

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