Inorder Successor/Predecessor in BST
MediumRemember the last turn you took
Problem
Given a BST and a key, find its in-order successor (next larger) and predecessor (next smaller).
The in-order successor is the smallest value greater than the key — go right, then left as far as possible.
The idea
Descend towards the key, and each time you move left record that node as the current best successor — it is the smallest value seen so far that exceeds the key. The predecessor is the mirror, recorded on right turns.
The trick
- Successor: record on left moves. Predecessor: record on right moves.
- If the node has a right subtree, the successor is that subtree's leftmost node.
- O(height) with no parent pointers required.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — BST {1,2,3,4,5}, key=3 Values: 1, 2, 3, 4, 5, 3.
1succ: cur=root; while cur: if cur.val>key: succ=cur; cur=cur.left else cur=cur.right2pred: mirror (go right when cur.val<key)Input
- array
- [1, 2, 3, 4, 5, 3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- bst = [8,4,12,2,6,10,14], key = 8
- Output:
- 10
- Explanation:
- The next bigger value after 8 is 10.
Example 2
- Input:
- bst = [2,1,3], key = 1
- Output:
- 2
- Explanation:
- Successor of 1 is 2.
Example 3
- Input:
- bst = [5], key = 5
- Output:
- -1
- Explanation:
- Nothing larger → -1.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.