BST Successor Search
Problem Description
Given the `root` of a **Binary Search Tree** and an integer `queryVal`, return the **in-order successor** of the node whose value equals `queryVal`. The in-order successor is the node with the smallest value that is **strictly greater than** `queryVal`.
If no such node exists (i.e., `queryVal` is the largest value in the BST), return `-1`.
You may assume `queryVal` exists in the tree.
**Example 1:**
```
8
/ \
3 11
/ \
1 6
```
Input: root = [8, 3, 11, 1, 6], queryVal = 3
Output: 6
Explanation: The in-order traversal is [1, 3, 6, 8, 11]. The successor of 3 is 6.
**Example 2:**
```
8
/ \
3 11
/ \
1 6
```
Input: root = [8, 3, 11, 1, 6], queryVal = 11
Output: -1
Explanation: 11 is the largest element; no successor exists.
Constraints
- The number of nodes in the tree is in the range [1, 5000].
- Node values are in the range [-10^5, 10^5].
- All node values are unique.
- queryVal is guaranteed to be a value present in the tree.
Follow-up
Can you extend this to also find the in-order predecessor (largest value strictly less than queryVal) in the same traversal pass?
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.