Lowest Common Ancestor of BST
Lowest Common Ancestor of BST: LCA of two nodes in a BST — exploit the ordering.
- The number of nodes in the tree is in the range [2, 10⁵].
- -10⁹ <= Node.val <= 10⁹
- All Node.val are unique.
- p != q
- p and q will exist in the BST.
Intuition
Finding the lowest common ancestor of a binary search tree is much easier than the same problem on a general binary tree, and the reason is worth being precise about. In a plain binary tree you must search both subtrees, because there is no way to tell which one contains a target without looking. A BST tells you immediately.
Stand at any node and compare it with the two targets p and q. If both are smaller, both live in the left subtree, so the current node cannot be their lowest common ancestor — the answer is somewhere left. If both are larger, the same reasoning sends you right. Those are the only two cases that move you.
Everything else means the node sits between them, and that is the answer:
- The first node where p and q fall on opposite sides — or where the node equals one of them — is the lowest common ancestor.
Why that node and not a deeper one? Because any node below it lies in only one of the two subtrees, so it can only contain one target. The split point is the last node whose subtree holds both, which is exactly the definition of the lowest common ancestor.
That gives a single downward walk with no recursion, no parent pointers, and no bookkeeping — just a comparison per level.
In a BST the LCA is simply the first node whose value falls between the two targets — because that's exactly where their search paths diverge. No recursion into both subtrees, no bookkeeping: one walk, one comparison per level. Compare this with the general binary-tree LCA, which must explore both sides precisely because it has no ordering to exploit.
Approach
Before reading on: price up what enumerating every case costs here, then ask what each node needs from its children before it can answer. Aim for O(h) time and O(1) space.
Compare both targets against the current node
At each node there are only three outcomes: both targets below, both above, or the node lies between them (inclusive). Two of the three move the cursor and the third is the answer, which is why no backtracking is ever needed.
Go left when both are smaller
If p.val and q.val are both less than node.val, both targets are in the left subtree. The current node has a target-free right side, so it cannot be the lowest common ancestor — move left.
Go right when both are larger
Symmetrically, if both target values exceed the node's, both live in the right subtree and the search continues there. Each such step discards the node and its entire opposite subtree with one comparison.
Return the first node that splits them
Otherwise the targets straddle this node, or the node is one of them. Either way this is the lowest common ancestor: no deeper node has both targets in its subtree, since going further commits to one side and loses the other.
Prefer the iterative loop
A while loop does this in O(1) space — the recursion is tail-recursive, so the call stack stores nothing useful. This is the version to write unless an interviewer specifically asks for recursion.
Cost compared with the general tree version
The walk takes one step per level, giving O(h) time — O(log n) on a balanced BST — and O(1) space. The binary-tree version has no ordering to exploit and must search both subtrees at O(n); the ordering property is the entire saving.
Solution & live demo
Common pitfalls
Using the general binary-tree algorithm
left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if left and right: return root
if node.val < lo: node = node.right elif node.val > hi: node = node.left else: return node
That works but visits every node, O(n), and ignores the ordering that makes this problem Easy rather than Medium. The BST tells you which way both targets lie, so only one path is ever walked.
Assuming p is smaller than q
if node.val < p.val: node = node.right elif node.val > q.val: node = node.left
lo, hi = sorted((p.val, q.val))
The problem doesn't promise any order between the two nodes. If q is the smaller one, both comparisons can fail simultaneously and the walk returns the wrong node. Normalising to lo/hi removes the assumption.
Excluding the targets themselves
if lo < node.val < hi: return node
else: return node # lo <= node.val <= hi
A node is allowed to be its own descendant's ancestor, so when node.val equals one of the targets that node is the LCA. Strict comparisons walk straight past it.
Edge cases
The walk stops at that target (it's not strictly less/greater on one side) — correct.
O(n) walk but same logic.