Lowest Common Ancestor of a Binary Search Tree

mediumTests passed 2026-11-11v1.0.0
TC: O(H)|SC: O(1)
TreesOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Walk down from `root` iteratively using the BST ordering property: if both `p.val` and `q.val` are strictly less than `curr.val`, go left; if both strictly greater, go right; otherwise `curr` is the split point (LCA).

2. Complexity Bounds & Proof

Visits at most one node per level along a single root-to-LCA path with iterative O(1) space.

3. Minimal Idiomatic Code

def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    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
    return curr

4. Failure Modes & Interview Follow-ups

Pitfalls:- Using general binary tree O(N) LCA ignores the BST ordering invariant and wastes O(H) stack. - Forgetting a node is a valid descendant of itself (`p == curr` or `q == curr` hits the split condition).
Follow-ups:- General Binary Tree LCA (not BST): post-order DFS returning non-null when left & right subtrees both find targets.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Validate Binary Search Tree (O(N))Kth Smallest Element in a BST (O(H + k))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.