Lowest Common Ancestor of a Binary Search Tree
Problem Statement
Given the root of a binary search tree and two nodes p and q that exist in the tree, return their lowest common ancestor. The lowest common ancestor is the lowest node that has both p and q as descendants, where a node may be a descendant of itself.
Input
A BST root and two existing tree nodes p and q.
Output
The node that is the lowest common ancestor of p and q.
Constraints
- •
2 <= number of nodes <= 10^5 - •
-10^9 <= Node.val <= 10^9 - •
All node values are unique - •
p and q exist in the BST - •
p != q
Examples
Example 1
root = **[6,2,8,0,4,7,9,null,null,3,5]**, p = **2**, q = **8**
**6**Example 2
root = **[6,2,8,0,4,7,9,null,null,3,5]**, p = **2**, q = **4**
**2**Learning Objectives
- Use BST ordering to move both target values left or right together.
- Identify the first split point as the lowest common ancestor.
- Handle the case where one target is the ancestor of the other.
- Contrast BST LCA with general binary-tree LCA, which cannot use ordering.
Intuition
Pattern Recognition
The signal is lowest common ancestor in a BST, not just any binary tree. In a general binary tree LCA problem, you usually need DFS to ask both subtrees whether they contain targets. In a BST, ordering gives a faster path: compare both target values with the current node.
If both targets are smaller than the current node, their LCA must be in the left subtree. If both are larger, it must be in the right subtree. Otherwise the current node is exactly where the paths split, or it is one of the targets, so it is the LCA. This is BST -> compare and branch applied to two values at once.
Common mistakes
- ×Using the general binary-tree LCA DFS and ignoring the BST ordering advantage.
- ×Moving left when only one target is smaller, even though that means the current node is the split point.
- ×Forgetting that if **current** equals **p** or **q**, it can be the LCA of itself and the other node.
- ×Comparing node object references in branch logic instead of comparing their values.
Algorithm Explanation
Key idea
At each node, compare the current value with both targets. If both targets lie on the same side, the LCA lies on that side too. The first node where the targets are not both left and not both right is the split point. That node is lowest because the search moved downward as long as both targets stayed together.
Recursion walkthrough
Use [5,3,8,2,4,7,9] with p = 2 and q = 4. Start at 5. Both target values are less than 5, so the LCA must be in the left subtree; move to 3. At 3, one target is less than 3 and the other is greater than 3. The paths split here, so 3 is the LCA.
For p = 4 and q = 9 in the same tree, start at 5. One target is less than 5 and the other is greater, so the root itself is the split point. For p = 3 and q = 4, the search reaches 3 and stops because 3 is one target and an ancestor of 4.
Algorithm
- Store the smaller target value as low and the larger as high.
- Start current at root.
- If high < current.val, both targets are left, so move to current.left.
- Else if low > current.val, both targets are right, so move to current.right.
- Otherwise current.val lies between the targets or equals one target, so return current.
- The problem guarantees both targets exist, so a valid BST input reaches an answer.
Solutions
Solution: Iterative split-point search
Use this as the default. It is shorter than the general-tree DFS, uses constant extra space, and directly demonstrates the BST ordering advantage.
Walk downward while both target values are on the same side of the current node. The first node where they are not on the same side is the LCA.
Step-by-step
- Compute low and high from p.val and q.val.
- Start at root.
- If high is smaller than current.val, move left because both targets are left.
- If low is greater than current.val, move right because both targets are right.
- Otherwise return current because it is the split point or one of the targets.
- Repeat until the answer is found.
O(h)
O(1)
The search follows one downward path: O(log n) for a balanced BST and O(n) for a skewed BST.
Java implementation
Dry Run
Sample input
root = [5,3,8,2,4,7,9], p = 2, q = 4. Track when the two target paths stop moving together.
| step | current node | target positions | action | reason |
|---|---|---|---|---|
| 1 | 5 | 2 and 4 are both less than 5 | move left | both targets must be in the left subtree |
| 2 | 3 | 2 is less than 3 and 4 is greater than 3 | return 3 | the target paths split at 3 |
The first split point is 3, so it is the lowest node that has both 2 and 4 below it or equal to it.
Interview Tips
Start by contrasting this with tree-lca, the general binary-tree LCA. In the general problem, you cannot know which subtree contains the targets without searching. In a BST, values tell you whether both targets are left, both are right, or the current node is the split point. That contrast is the whole interview insight.
Likely follow-ups
- How would you solve LCA in a general binary tree without BST ordering?
- What changes if one or both target nodes might not exist in the tree?
- How would parent pointers change the solution?
- How would you answer many LCA queries on a mostly static BST?
Similar Problems
Key Takeaways
- In a BST, LCA is the first node where target values split across sides or equal the current node.
- If both targets are smaller, move left; if both are larger, move right.
- The current node can be the LCA when it is one of the targets.
- General binary-tree LCA cannot use this ordering shortcut.