Mid/Senior
Inorder Successor in BST
Given the root of a binary search tree and an integer p representing the value of a node in that tree, find the inorder successor of that node.
The inorder successor of a node p is the node with the smallest value greater than p.val. Equivalently, it is the node that appears immediately after p in an inorder traversal of the BST.
Return the value of the inorder successor. If p has no inorder successor, return null.
Example 1
2
/ \
1 3Input
root = [2,1,3], p = 1Output
2The inorder traversal is [1, 2, 3], so the node after 1 is 2.
Example 2
5
/ \
3 6
/ \
2 4
/
1Input
root = [5,3,6,2,4,null,null,1], p = 6Output
nullThe node with value 6 is the largest value in the BST, so it has no inorder successor.
Constraints
- 1 <= number of nodes in the tree <= 10^4
- -10^5 <= Node.val <= 10^5
- All node values are unique.
- p is the value of a node in the BST.