LCA in BST
MediumDescend until the values split
Problem
Return the lowest common ancestor of two nodes in a BST.
Walk down while both targets are on the same side; the first node that splits them is the LCA.
The idea
If both targets are smaller than the current node go left, if both are larger go right; the first node where they diverge — or which equals one of them — is the lowest common ancestor. No subtree search is needed at all.
The trick
- The split point is the answer; you never look at both subtrees.
- O(height), much cheaper than the general binary-tree version.
Step 1 of 3. Find the LCA of 1 and 4. Use the ordering: both smaller → go left, both larger → go right.
Turn where they diverge.
1while (node) {2 if (p < node.val && q < node.val) node = node.left;3 else if (p > node.val && q > node.val) node = node.right;4 else return node; // the split point5}Input
- nodes
- 7, 6 edges
Memory
- node
- —
Output
- LCA
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- bst = [6,2,8,0,4,7,9], p = 2, q = 8
- Output:
- 6
- Explanation:
- They split at the root 6.
Example 2
- Input:
- bst = [6,2,8,0,4,7,9], p = 2, q = 4
- Output:
- 2
- Explanation:
- 2 is the ancestor of 4.
Example 3
- Input:
- bst = [2,1,3], p = 1, q = 3
- Output:
- 2
- Explanation:
- They meet at 2.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.