Lowest Common Ancestor of a BST
Maintained by Vikas D, software engineer
You receive a binary search tree encoded as a level-order array, the same layout used on most judges, where null marks a slot with no node. Two values p and q are also given, and both are guaranteed to exist as nodes in the tree.
The lowest common ancestor of p and q is the node furthest from the root that still has both p and q in its subtree. A node is considered part of its own subtree, so if one of the two values sits directly above the other on the path from the root, that higher value is the answer.
Return the value stored at that ancestor node, not the node object itself. Because every value in a BST is unique, there is exactly one correct answer.
The structure being a BST is the part worth exploiting: at any node you can tell which side each target falls on purely by comparing values, which means you never have to search blindly.
Examples
2 lives in the left subtree of the root and 8 lives in the right subtree, so the two paths split at the root 6. No node deeper than 6 holds both, making 6 the answer.
4 is a descendant of 2 (2 has children 0 and 4). Since a node is its own descendant, 2 contains both targets and nothing below 2 does, so 2 is the lowest common ancestor.
Both 3 and 5 hang under node 4 (3 is its left child, 5 its right child). They first share an ancestor at 4, so 4 is returned.
Constraints
- The input array always describes a valid BST.
- All node values are distinct.
- Between 2 and 10^5 nodes.
- Both p and q are present in the tree, so an answer always exists.
Visible test cases
- lcaBST([6,2,8,0,4,7,9,null,null,3,5], 2, 8) == 6
- lcaBST([6,2,8,0,4,7,9,null,null,3,5], 2, 4) == 2
- lcaBST([6,2,8,0,4,7,9,null,null,3,5], 3, 5) == 4
- lcaBST([6,2,8,0,4,7,9,null,null,3,5], 7, 9) == 8
- lcaBST([4,2,6,1,3,5,7], 1, 3) == 2
- lcaBST([4,2,6,1,3,5,7], 5, 7) == 6
Hints
Hint 1
You do not need to compare the two targets against every node. The BST ordering tells you, at each node, whether a value lives to the left, to the right, or right here.
Hint 2
Walk down from the root. If both p and q are smaller than the current value, the split has not happened yet, so go left. If both are larger, go right.
Hint 3
The first node where p and q do not both fall on the same side (one is smaller and one is larger, or one equals the node) is the lowest common ancestor. Stop and return it.
Approaches
Collect both root-to-node paths
Time O(n) · Space O(n)Treat it like a generic binary tree: find the full path from the root down to p and the full path down to q, then walk both paths together and take the last node they share.
- Rebuild the tree from the level-order array into linked nodes.
- Search for p, recording every node visited from the root, and do the same for q.
- Compare the two recorded paths position by position from the start.
- Return the deepest node where the two paths still match; that is where they diverge.
Single BST walk
Time O(h) for the walk, where h is the tree height (O(n) to build the tree from the array) · Space O(1) extra for the walk (O(n) for the rebuilt tree)Use the ordering property: at each node, the comparison of p and q against the current value tells you instantly which subtree both belong to, or that the split point has been reached.
- Rebuild the tree, then start a pointer at the root.
- If both p and q are less than the current value, move the pointer to the left child.
- If both p and q are greater, move the pointer to the right child.
- Otherwise the targets straddle the current value (or one equals it), so return the current value as the lowest common ancestor.
Common mistakes
- Forgetting that a node is its own ancestor. When q sits directly below p, the answer is p, not some node above it. The walk handles this because the equality case ends the loop.
- Assuming p is always smaller than q. The inputs can arrive in either order, so compare both against the current value rather than relying on which one is the lesser.
- Comparing positions instead of values. The BST property is about value ordering, so route on val, not on array index or depth.
- Mishandling the null markers when rebuilding the tree from the level-order array; a null slot must not consume a child pointer incorrectly or the reconstructed tree will be wrong.
Follow-up variations
- What changes if it is an ordinary binary tree with no ordering? You can no longer route by comparison and must recurse, returning a node when p and q surface in different subtrees.
- What if p or q might be absent from the tree? You would need to confirm both exist before trusting the answer.
- If the nodes carried parent pointers, how would you find the LCA without recursion or extra arrays?
- How would you answer many LCA queries on the same static tree efficiently, for example with binary lifting or Euler-tour plus range-minimum?