Lowest Common Ancestor of a BST
A medium BST interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- BST
- Sheets
- 3
- Core for
- 2 roles
The problem
Given the root of a binary search tree and two nodes p and q, return the lowest common ancestor of these two nodes. In a BST, the LCA is the deepest node that has both p and q as descendants, and it can be found by comparing node values with the root.
Example 1
- Input
- root=[6,2,8,0,4,7,9,null,null,3,5], p=2, q=8
- Output
- 6
- Why
- Since p=2 < root=6 and q=8 > root=6, the LCA is the root 6.
Example 2
- Input
- root=[6,2,8,0,4,7,9,null,null,3,5], p=2, q=4
- Output
- 2
- Why
- Both p=2 and q=4 are in the left subtree of 6, but 4 is in the right subtree of 2, so 2 is the LCA.
Example 3
- Input
- root=[2,1], p=1, q=2
- Output
- 2
- Why
- Node 2 is the root and ancestor of node 1.
Constraints
- The number of nodes is in the range [2, 105].
- -109 <= Node.val <= 109
- All Node.val are unique.
- p and q will exist in the BST.
How to think about it
Updated 2026-09-09In a general binary tree you have to inspect both subtrees and merge findings, but a BST provides total order. If both targets sit on the left, the split point is further left; if both sit on the right, it is further right. The very first node where they diverge or one matches the current node is guaranteed to be the ancestor.
Approaches, worst first
Path recording and mismatch search
time O(h) · space O(h)
Trace the root-to-p path and root-to-q path into two lists by searching from root. Then compare the paths from the start until they diverge. Works correctly but allocates memory for path arrays when a single pointer walk suffices.
Recursive divide and split
time O(h) · space O(h)
If p and q are both smaller than root, recurse on root.left; if both are larger, recurse on root.right; otherwise root is the split point. Elegantly concise, though it consumes stack frames proportional to tree height.
Iterative split walkWrite this one
time O(h) · space O(1)
Walk a single pointer down from root in a while loop using the same comparison logic. Because there is no backtracking once a subtree is chosen, no stack is necessary and auxiliary space drops to constant.
Where people lose marks · 2
- Assuming p is always less than q. If q < p, checking `p.val < root.val && root.val < q.val` fails unless the values are sorted beforehand or checked symmetrically.
- Missing the case where p or q is itself the ancestor. When current equals p or q, the traversal must halt immediately and return current, rather than continuing downwards.
The theory behind it
BST — the ground this problem stands on. All BST problems
What BST is
A binary search tree is a binary tree that enforces a strict ordering rule at every node. Every value stored in a node's left branch must be smaller than the node itself, and every value in its right branch must be larger. Because this rule holds true everywhere down the tree, searching for a value does not require checking every branch. At each step, a single comparison lets you discard an entire half of the remaining nodes.
When to reach for it
Reach for a binary search tree when problems mention sorted tree structures, finding the kth smallest element, checking tree validity, or searching within a range of values. Signals include queries for the next greater element in a dynamic set, finding the lowest common ancestor in a sorted tree, or converting sorted arrays into height-balanced trees. When data must remain sorted while supporting continuous insertions and lookups, BST properties are the target.
How the pattern works
Use the ordering property to prune entire subtrees. When looking for a key, move left if the target is smaller than the current node, or move right if it is larger, stopping when values match or when reaching a null link. For validating a tree, do not merely compare a node to its immediate children; pass valid lower and upper value bounds down through recursive calls. Walking a valid binary search tree in-order visits all values in strictly increasing numerical order.
More BST problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .