Description
Given a BST and a node p in it, return the in-order successor of that node. If it doesn't exist, return null.
Examples
Input:
root = [2,1,3], p = 1Output:
2Explanation:
The in-order successor of 1 is 2.
Input:
root = [1], p = 1Output:
1Explanation:
Edge case with a single-element array.
Input:
root = [5,3,8,2,4,7,9], p = 4Output:
5Explanation:
In the BST with in-order traversal [2,3,4,5,7,8,9], node 4's in-order successor is 5. Since 4 has no right subtree, looking for the nearest ancestor where 4 would be in the left subtree.
Constraints
- •
1 ≤ number of nodes ≤ 10⁴ - •
-10⁵ ≤ Node.val ≤ 10⁵