#235
Lowest Common Ancestor of a Binary Search Tree
Medium Split point
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the lowest common ancestor of two nodes p and q in a BST.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the split point of p and q.
Why this works: both smaller → go left; both bigger → go right; otherwise you're at the split.
Example: tree 6 (2 (0, 4), 8 (7, 9)), p 2, q 8
2 < 6 < 8 → split at 6✦Hints open one at a time
If both values are smaller than the current node, the LCA is on the left.
If both are larger, it's on the right. Otherwise, the current node is where they split.
↗Approach
Walk down from the root using the comparisons above. The first node where p and q are not on the same side (or equal to one of them) is the LCA.
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode cur = root;
while (true) {
if (p.val < cur.val && q.val < cur.val) cur = cur.left;
else if (p.val > cur.val && q.val > cur.val) cur = cur.right;
else return cur; // they split here
}
}
}!Common mistake
Using the general binary-tree LCA — it works but doesn't use the BST ordering.
Complexity
- Time: O(h).
- Space: O(1).
Topic: Binary Search Trees
🎬 Episodes 61–63: video coming soon