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

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

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

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
    if (!root || root === p || root === q) return root;             // L1: base cases
    const left = lowestCommonAncestor(root.left, p, q);            // L2: search left subtree
    const right = lowestCommonAncestor(root.right, p, q);          // L3: search right subtree
    if (left && right) return root;                                 // L4: split point found
    return left ?? right;                                           // L5: propagate up
}

final class Solution { func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? { guard let root else { return nil }; if root === p || root === q { return root }; let left = lowestCommonAncestor(root.left, p, q); let right = lowestCommonAncestor(root.right, p, q); if left != nil && right != nil { return root }; return left ?? right } }

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

function lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode): TreeNode {
    if (p.val < root.val && q.val < root.val)
        return lowestCommonAncestor(root.left!, p, q);   // L1: both left
    if (p.val > root.val && q.val > root.val)
        return lowestCommonAncestor(root.right!, p, q);  // L2: both right
    return root;                                          // L3: split point
}

final class Solution { func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? { guard let root, let p, let q else { return nil }; if p.val < root.val && q.val < root.val { return lowestCommonAncestor(root.left, p, q) }; if p.val > root.val && q.val > root.val { return lowestCommonAncestor(root.right, p, q) }; return root } }

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)$ .

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

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

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
    while (root) {
        if (p.val < root.val && q.val < root.val)
            root = root.left;          // L1: move left
        else if (p.val > root.val && q.val > root.val)
            root = root.right;         // L2: move right
        else
            return root;               // L3: found split
    }
    return null;
}

final class Solution { func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? { guard let p, let q else { return nil }; var current = root; while let node = current { if p.val < node.val && q.val < node.val { current = node.left } else if p.val > node.val && q.val > node.val { current = node.right } else { return node } }; return nil } }

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

Python
TypeScript

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()

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function buildTree(vals: (number | null)[]): TreeNode | null {
    if (!vals.length) return null;
    const root = new TreeNode(vals[0] as number);
    const q: TreeNode[] = [root];
    let i = 1;
    while (q.length && i < vals.length) {
        const node = q.shift()!;
        if (i < vals.length && vals[i] !== null) { node.left = new TreeNode(vals[i] as number); q.push(node.left); }
        i++;
        if (i < vals.length && vals[i] !== null) { node.right = new TreeNode(vals[i] as number); q.push(node.right); }
        i++;
    }
    return root;
}

function findNode(root: TreeNode | null, val: number): TreeNode | null {
    while (root) {
        if (val === root.val) return root;
        root = val < root.val ? root.left : root.right;
    }
    return null;
}

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
    while (root) {
        if (p.val < root.val && q.val < root.val) root = root.left;
        else if (p.val > root.val && q.val > root.val) root = root.right;
        else return root;
    }
    return null;
}

const t = buildTree([6, 2, 8, 0, 4, 7, 9, null, null, 3, 5])!;
console.assert(lowestCommonAncestor(t, findNode(t, 2)!, findNode(t, 8)!)!.val === 6);
console.assert(lowestCommonAncestor(t, findNode(t, 2)!, findNode(t, 4)!)!.val === 2);
console.assert(lowestCommonAncestor(t, findNode(t, 0)!, findNode(t, 5)!)!.val === 2);
const t2 = buildTree([4, 2, 6, 1, 3, 5, 7])!;
console.assert(lowestCommonAncestor(t2, findNode(t2, 5)!, findNode(t2, 7)!)!.val === 6);
console.log("all tests pass");

Binary Trees & BSTs, BST ordering invariant; iterative walk

Tree Traversal, the recursive or iterative visit pattern for carrying path and subtree state.
DFS, the depth first traversal habit of following one branch before returning.

235. Lowest Common Ancestor of a BST (Medium)

Problem

Try it yourself

Approach 1: Generic LCA (ignore BST property)

Approach 2: Recursive BST walk

Approach 3: Iterative BST walk (optimal space)

Summary

Test cases

Related data structures

Related concepts