Lowest Common Ancestor in a BST
MediumThe split point of the two values
Walk down from the top; when the two targets split to different sides, that node is their meeting point.
The idea
Use the ordering: if both values are smaller than the node go left, if both are larger go right. The first node that sits between them (or equals one) is their LCA.
Step 1 of 3. Find the LCA of 1 and 4. Use the ordering: both smaller → go left, both larger → go right.
1/3
Optimal
timeO(h)spaceO(1)
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.