519. Next Key Up
A race organiser keeps finishing times in a binary search tree. For the runner stored in node p, she wants the runner who finished immediately after, that is, the node holding the smallest key that is strictly larger than the key of p.
Return a reference to that node of root (the node itself, not a copy), or null if p already has the largest key in the tree. The node p is guaranteed to belong to the tree, and the nodes do not store parent pointers, so you cannot climb upward from p; work from root instead.
Example 1
- Input:
- root = [20,10,30,5,15,25,40], p = {"nodeOf":0,"val":15}
- Output:
- 0
- Explanation:
Node 15 has no right child, so the next larger key is its nearest ancestor reached from the left, which is 20.
Example 2
- Input:
- root = [20,10,30,5,15,25,40], p = {"nodeOf":0,"val":40}
- Output:
- null
- Explanation:
40 is the largest key, so there is no successor and the answer is null.
Constraints
1 ≤ number of nodes ≤ 104
-1000 ≤ node key ≤ 1000, all keys distinct
root is a valid binary search tree and p is one of its nodes.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(h)
- Space
- O(1)