Trees · LC #235
Lowest Common Ancestor of BST
Find the LCA of two nodes in a BST by exploiting sorted ordering: navigate left if both targets are smaller, right if both are larger, otherwise the current node is the split point.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given a binary search tree (BST) and two nodes p and q, find their lowest common ancestor. The LCA is the lowest node that has both p and q as descendants (a node can be a descendant of itself).
Sample I/O
Input: root=[6,2,8,0,4,7,9,null,null,3,5], p=2, q=8 Output: 6 Input: same tree, p=2, q=4 Output: 2 (2 is ancestor of 4)
Time: O(h) · Space: O(1)
Intuition
How to Think About It
Intuition
BST ordering lets us navigate deterministically without exploring both subtrees. If both p and q are less than current node, LCA must be in the left subtree. If both are greater, go right. The moment they split (or one equals current), the current node IS the LCA.
Core Concept
Iterative or recursive: if p.val < root.val AND q.val < root.val → go left. If both greater → go right. Otherwise → current node is the LCA (split point or one node equals root). No need to explore both subtrees - O(h) time.
When to use
LCA on BSTs exclusively. Always prefer over the general O(n) binary tree LCA when BST property is guaranteed.
When NOT to use
General binary trees (no ordering guarantee) - use the general LCA algorithm instead.
Key Insights
What to Know Cold
- BST property eliminates need to search both subtrees - O(h) vs O(n).
- The "split point" condition: one target ≤ root ≤ other target (or root equals one).
- Iterative version uses no stack space - O(1) space.
- Works even when p is an ancestor of q (handled by equality check).
- Equivalent to binary search - each step eliminates one subtree.
1 example
Worked Examples
Split point at root
BST root=6, p=2 (left), q=8 (right) - they straddle the root.
2 < 6 and 8 > 6 → split at 6 → LCA = 6.
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
let node = root;
while (node) {
if (p.val < node.val && q.val < node.val) node = node.left;
else if (p.val > node.val && q.val > node.val) node = node.right;
else return node;
}
return null;
}Output: Node 6
O(h) solution - contrast with O(n) general binary tree approach.