Lowest Common Ancestor of a BST

Difficulty: Medium Source: NeetCode

Problem

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. The lowest common ancestor is defined as “the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1: Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6

Example 2: Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output: 2

Constraints:

• The number of nodes in the tree is in the range [2, 10^5]
• -10^9 <= Node.val <= 10^9
• All Node.val are unique
• p != q
• p and q will exist in the BST

Prerequisites

Before attempting this problem, you should be comfortable with:

• BST Property — Left subtree values < node value < right subtree values
• LCA Concept — The deepest node that has both target nodes in its subtree
• Binary Search — Using the BST property to eliminate half the tree at each step

1. Recursive (Using BST Property)

Intuition

The BST property lets us decide which direction to go without exploring both sides. If both p and q are smaller than the current node, the LCA must be in the left subtree. If both are larger, it’s in the right subtree. If they’re on opposite sides (or one equals the current node), the current node is the LCA.

Algorithm

1. If both p.val and q.val are less than root.val, recurse left
2. If both are greater than root.val, recurse right
3. Otherwise, root is the LCA — return it

Solution

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

def lowest_common_ancestor_recursive(root, p, q):
    # Both smaller → LCA is in left subtree
    if p.val < root.val and q.val < root.val:
        return lowest_common_ancestor_recursive(root.left, p, q)
    # Both larger → LCA is in right subtree
    if p.val > root.val and q.val > root.val:
        return lowest_common_ancestor_recursive(root.right, p, q)
    # Split point: one is left, one is right (or one equals root)
    return root

# --- helpers ---
def build_bst_from_sorted(values):
    """Build BST from level-order list."""
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

def find_node(root, val):
    """Find a node by value in the BST."""
    while root:
        if val == root.val:
            return root
        elif val < root.val:
            root = root.left
        else:
            root = root.right
    return None

# --- tests ---
# BST: [6,2,8,0,4,7,9,null,null,3,5]
root = build_bst_from_sorted([6, 2, 8, 0, 4, 7, 9, None, None, 3, 5])

p = find_node(root, 2)
q = find_node(root, 8)
lca = lowest_common_ancestor_recursive(root, p, q)
print(lca.val)  # 6

p = find_node(root, 2)
q = find_node(root, 4)
lca = lowest_common_ancestor_recursive(root, p, q)
print(lca.val)  # 2

Complexity

• Time: O(h) — at each level we go either left or right; O(log n) for balanced BST, O(n) worst case
• Space: O(h) — recursion stack depth

2. Iterative (O(h) Time, O(1) Space)

Intuition

The recursive version has O(h) stack overhead. We can eliminate that by iterating with a pointer, making this the most space-efficient approach.

Solution

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

def lowest_common_ancestor_iterative(root, p, q):
    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  # Split point found

    return None  # Should never reach here given the constraints

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.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

# --- tests ---
root = build_tree([6, 2, 8, 0, 4, 7, 9, None, None, 3, 5])

p = find_node(root, 2)
q = find_node(root, 8)
print(lowest_common_ancestor_iterative(root, p, q).val)  # 6

p = find_node(root, 2)
q = find_node(root, 4)
print(lowest_common_ancestor_iterative(root, p, q).val)  # 2

Complexity

• Time: O(h) — same as recursive
• Space: O(1) — no recursion stack

Common Pitfalls

Using a general tree LCA algorithm on a BST. The BST property lets you solve this in O(h) without exploring both subtrees. A general LCA algorithm that ignores this property runs in O(n) — less efficient.

Not handling the case where p or q equals root. If p.val == root.val or q.val == root.val, neither the left nor right condition triggers, so we fall through to return root — which is correct because a node is a descendant of itself.