02
Intuition
In a BST you don't need to search both sides: if both targets are smaller than the current node, the LCA is left; both bigger, it's right. The first node between them (inclusive) is the split point — and the LCA.
03
Approach
1
Walk, don't recurse everywhere
From the root: both p,q < node → left. Both > node → right. Otherwise node splits them → answer.
2
Why the split is the LCA
Any deeper node loses one of the targets to the other side — the split point is the last common node on both search paths.
3
Iterative one-liner walk
No stack, no parent pointers, O(h).
04
Solution & live demo
python
▶1class Solution:
▶2 def lowestCommonAncestor(self, root, p, q):
▶3 lo, hi = sorted((p.val, q.val))
▶4 node = root
▶5 while node:
▶6 if node.val < lo: node = node.right
▶7 elif node.val > hi: node = node.left
▶8 else: return node
05
Edge cases
One target is the other's ancestor
The walk stops at that target (it's not strictly less/greater on one side) — correct.
Degenerate chain BST
O(n) walk but same logic.
06
Complexity
Time
O(h)
Space
O(1)
Single descent, no subtree exploration.