LCA in BST
Lowest Common Ancestor: start at the root. If both target nodes are smaller, go left. If both are larger, go right. If they split (one left, one right), you're at the LCA. The BST ordering makes this O(h).
How It Works
Finding the lowest common ancestor in a BST needs no parent pointers or path recording, because the ordering tells you where both targets live. Start at the root and compare: if both target values are smaller than the current node, the LCA must be in the left subtree; if both are larger, go right. The first node where the targets split — one on each side, or the node equals one of the targets — is the LCA, since descending further would abandon one of them.
This walks a single root-to-LCA path, so time is O(h) — O(log n) on balanced trees — and space is O(1) iteratively. Contrast with the general binary-tree LCA, which lacks ordering and must recurse through subtrees in O(n). The technique is really binary search wearing a tree costume: each comparison discards an entire subtree.
Step-by-Step Visualization
Code
static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root != null) {
if (p.val < root.val && q.val < root.val) {
root = root.left;
} else if (p.val > root.val && q.val > root.val) {
root = root.right;
} else {
return root; // Split point = LCA
}
}
return null;
}Tips & Gotchas
Practice Problems
- 1Lowest Common Ancestor of a Binary Search Tree
- 2Lowest Common Ancestor of a Binary Tree
- 3Inorder Successor in BST
- 4Insert into a Binary Search Tree
About the BST Patterns Pattern
Binary Search Trees guarantee: everything in the left subtree < root < everything in the right subtree. This property lets you make decisions at each node about which direction to go, effectively doing binary search on a tree.
Tree problems are almost always DFS (recursion) or BFS (level-order). The pattern: solve for children, combine results, return up. BST's sorted property lets you prune half the tree.
Common Trees Interview Problems
- Maximum Depth of Binary Tree
- Validate BST
- Binary Tree Level Order Traversal
- Lowest Common Ancestor
- Serialize and Deserialize Binary Tree
- Diameter of Binary Tree
Frequently Asked Questions
How does BST LCA differ from LCA in a general binary tree?
In a BST, value comparisons at each node point you toward both targets simultaneously, giving an O(h) walk with O(1) space. A general binary tree has no ordering, so you must search both subtrees recursively — the node where the two targets appear in different subtrees is the LCA, costing O(n).
What happens when one target node is an ancestor of the other?
The walk stops exactly at that ancestor: the split condition triggers because one value equals the current node while the other lies in one of its subtrees. By the standard definition a node counts as its own ancestor, so this is the correct LCA.