Lowest Common Ancestor of a Binary Search Tree (LeetCode 235)
You're given a binary search tree (BST) and two of its nodes, p and q. Find their lowest common ancestor (LCA): the deepest node in the tree that still counts p and q among its descendants.
By convention a node is its own descendant, so if one of p/q sits directly above the other, that higher node is the LCA.
Worked Examples
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 86root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 42root = [2,1], p = 2, q = 122 is the parent of 1, and a node counts as its own descendant, so the answer is 2.⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[2, 105].-109 <= Node.val <= 109All
Node.valare unique.p != qpandqwill exist in the BST.
Core Insight
BST ordering guarantees that the first node separating p and q is their unique lowest common ancestor.
Real-World Scenario & Production Applications
Hierarchical permission inheritance resolution, IP routing prefix common ancestor search.
Step-by-Step Execution Trace Table
| Node | p.val vs Node | q.val vs Node | Decision |
|---|---|---|---|
| 6 | 2 < 6 (left) | 8 > 6 (right) | Split Point! Return Node 6 |
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 86| Node | p.val vs Node | q.val vs Node | Decision |
|---|---|---|---|
| 6 | 2 < 6 (left) | 8 > 6 (right) | Split Point! Return Node 6 |
| 1 | curr = root |
| 2 | while curr: |
| 3 | if p.val < curr.val and q.val < curr.val: |
| 4 | curr = curr.left |
| 5 | elif p.val > curr.val and q.val > curr.val: |
| 6 | curr = curr.right |
| 7 | else: |
| 8 | return curr |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Finding the lowest common ancestor sounds like it should require exploring both subtrees fully — but a BST's ordering means you already know, at every node, which single direction to walk.
🛣️ The Analogy: A Fork in the Road
Imagine walking from the root toward two destinations, p and q, on a road system where "smaller values are always to the left, larger values are always to the right." As long as both destinations are still on the same side of the road you're currently standing on, keep walking in that one direction — there's no reason to check the other side, since neither destination is there. The moment the two destinations are no longer on the same side (one is smaller, one is larger, or you've arrived at one of them directly), you're standing at the exact fork where their paths first diverge — and that fork is the lowest common ancestor.
🔑 The Key Idea in the Code
Only one recursive call ever fires per level, not two — this is a genuine binary-search-style single-direction walk, not a full traversal.
Traversing both subtrees like a generic binary tree: In a BST, if
p.val < root.val and q.val < root.val, LCA is GUARANTEED in the left subtree. Searching both subtrees wastes time instead of .Assuming order: The problem does not guarantee
p.val < q.val. Always checkmin(p.val, q.val) <= root.val <= max(p.val, q.val).LCA can be or itself: If
root.val == p.valorroot.val == q.val,rootis the LCA. Do not descend further.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
LCA query on a Binary Search Tree.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: the LCA is the unique highest node where p and q diverge into different subtrees.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Using general binary tree post-order traversal: correct but wastes
O(N)time when BST ordering allows O(H).Overcomplicating the split condition: simply check if both values are on the same side.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I iterate from root. If both p.val and q.val are less than curr.val, I move left. If both are greater, I move right. The first node where they split (or where curr matches p or q) is the LCA. Runs in O(H) time and
O(1)auxiliary space."
Complexity & Mathematical Proof
O(H)
Look at the execution steps: If both p and q are smaller than root, LCA is in left subtree; if both are larger, LCA is in right subtree; if they split, current node is the LCA. Single path traversal.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative loop (or O(H) if recursive). Iterative while loop stores only curr pointer in O(1) space.
T(H) = H steps = O(H)
Derivation Progression
(p.val - curr.val) · (q.val - curr.val) ≤ 0
When p and q lie on opposite sides of curr (or one equals curr), curr is the unique LCA.
curr = curr.left if p.val < curr.val else curr.right
Descends strictly toward the LCA node.
H iterations
Terminates in at most H steps.
Variable Definitions
Total number of nodes in the BST
Tree height (log N in balanced tree, N in skewed tree)
Memory Architecture & Bounds
O(1) Iterative loop (or O(H) if recursive)
O(1) Single pointer variable curr
O(1) Node reference
Boundary Best / Worst Cases
if root is LCA.
.
if LCA is deep leaf ( skewed, balanced).
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "lowest common ancestor of a binary search tree". BST ordering invariant: if both and are smaller than curr.val, LCA must lie in the left subtree; if both are greater, LCA must lie in the right subtree; if and split across curr.val (or one equals curr.val), curr IS the LCA!
. Time budget without recursion or stack allocation.
Treating it as a general binary tree (LC 236): in a BST, no backtracking or subtree post-order passes are needed; directional branching runs in extra space.
Lowest Common Ancestor of a Binary Search Tree (LeetCode 235)
You're given a binary search tree (BST) and two of its nodes, p and q. Find their lowest common ancestor (LCA): the deepest node in the tree that still counts p and q among its descendants.
By convention a node is its own descendant, so if one of p/q sits directly above the other, that higher node is the LCA.
Worked Examples
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 86root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 42root = [2,1], p = 2, q = 122 is the parent of 1, and a node counts as its own descendant, so the answer is 2.⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[2, 105].-109 <= Node.val <= 109All
Node.valare unique.p != qpandqwill exist in the BST.
Core Insight
BST ordering guarantees that the first node separating p and q is their unique lowest common ancestor.
Real-World Scenario & Production Applications
Hierarchical permission inheritance resolution, IP routing prefix common ancestor search.
Step-by-Step Execution Trace Table
| Node | p.val vs Node | q.val vs Node | Decision |
|---|---|---|---|
| 6 | 2 < 6 (left) | 8 > 6 (right) | Split Point! Return Node 6 |
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 86| Node | p.val vs Node | q.val vs Node | Decision |
|---|---|---|---|
| 6 | 2 < 6 (left) | 8 > 6 (right) | Split Point! Return Node 6 |
| 1 | curr = root |
| 2 | while curr: |
| 3 | if p.val < curr.val and q.val < curr.val: |
| 4 | curr = curr.left |
| 5 | elif p.val > curr.val and q.val > curr.val: |
| 6 | curr = curr.right |
| 7 | else: |
| 8 | return curr |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Finding the lowest common ancestor sounds like it should require exploring both subtrees fully — but a BST's ordering means you already know, at every node, which single direction to walk.
🛣️ The Analogy: A Fork in the Road
Imagine walking from the root toward two destinations, p and q, on a road system where "smaller values are always to the left, larger values are always to the right." As long as both destinations are still on the same side of the road you're currently standing on, keep walking in that one direction — there's no reason to check the other side, since neither destination is there. The moment the two destinations are no longer on the same side (one is smaller, one is larger, or you've arrived at one of them directly), you're standing at the exact fork where their paths first diverge — and that fork is the lowest common ancestor.
🔑 The Key Idea in the Code
Only one recursive call ever fires per level, not two — this is a genuine binary-search-style single-direction walk, not a full traversal.
Traversing both subtrees like a generic binary tree: In a BST, if
p.val < root.val and q.val < root.val, LCA is GUARANTEED in the left subtree. Searching both subtrees wastes time instead of .Assuming order: The problem does not guarantee
p.val < q.val. Always checkmin(p.val, q.val) <= root.val <= max(p.val, q.val).LCA can be or itself: If
root.val == p.valorroot.val == q.val,rootis the LCA. Do not descend further.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
LCA query on a Binary Search Tree.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: the LCA is the unique highest node where p and q diverge into different subtrees.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Using general binary tree post-order traversal: correct but wastes
O(N)time when BST ordering allows O(H).Overcomplicating the split condition: simply check if both values are on the same side.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I iterate from root. If both p.val and q.val are less than curr.val, I move left. If both are greater, I move right. The first node where they split (or where curr matches p or q) is the LCA. Runs in O(H) time and
O(1)auxiliary space."
Complexity & Mathematical Proof
O(H)
Look at the execution steps: If both p and q are smaller than root, LCA is in left subtree; if both are larger, LCA is in right subtree; if they split, current node is the LCA. Single path traversal.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative loop (or O(H) if recursive). Iterative while loop stores only curr pointer in O(1) space.
T(H) = H steps = O(H)
Derivation Progression
(p.val - curr.val) · (q.val - curr.val) ≤ 0
When p and q lie on opposite sides of curr (or one equals curr), curr is the unique LCA.
curr = curr.left if p.val < curr.val else curr.right
Descends strictly toward the LCA node.
H iterations
Terminates in at most H steps.
Variable Definitions
Total number of nodes in the BST
Tree height (log N in balanced tree, N in skewed tree)
Memory Architecture & Bounds
O(1) Iterative loop (or O(H) if recursive)
O(1) Single pointer variable curr
O(1) Node reference
Boundary Best / Worst Cases
if root is LCA.
.
if LCA is deep leaf ( skewed, balanced).
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "lowest common ancestor of a binary search tree". BST ordering invariant: if both and are smaller than curr.val, LCA must lie in the left subtree; if both are greater, LCA must lie in the right subtree; if and split across curr.val (or one equals curr.val), curr IS the LCA!
. Time budget without recursion or stack allocation.
Treating it as a general binary tree (LC 236): in a BST, no backtracking or subtree post-order passes are needed; directional branching runs in extra space.