Which Stored Value Comes Right Before a Key
Implement predecessorOf
You are given the root of a binary search tree with distinct values and an integer key (the key need not be in the tree). Return the value that comes immediately before key in the ascending order of the tree's values — the largest value strictly smaller than key — or -1 if no value is smaller.
A list of all values makes this a simple scan. Walking down the tree once and remembering the last node where you turned right finds it directly.
Example 1:
Input: root = [42,18,66,9,30,54,80,null,null,24,36,null,60], key = 36
Output: 30
Example 2:
Input: root = [42,18,66,9,30,54,80,null,null,24,36,null,60], key = 42
Output: 36
Example 3:
Input: root = [42,18,66,9,30,54,80,null,null,24,36,null,60], key = 9
Output: -1
+ 14 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000 - ●
The tree is a binary search tree (left subtree smaller, right subtree larger at every node), given by its root node - ●
key is any integer between 0 and 1000 (it does not have to be in the tree) - ●
Return the value that comes immediately before key when the tree's values are listed in ascending order — that is, the largest value that is STRICTLY smaller than key. If there is none, return -1
root =
key =