A shoe shop stores the sizes it has in stock in a binary search tree with distinct values. A customer asks for size x. Return [floor, ceiling] where floor is the largest stocked size at most x and ceiling is the smallest stocked size at least x. Use None for a side that does not exist. If x itself is stocked, both are x.
Examples
20
/ \
10 30
/ \ / \
5 15 25 40
Input: root = build_tree([20, 10, 30, 5, 15, 25, 40]), x = 17
Output: [15, 20]
Input: root = build_tree([20, 10, 30, 5, 15, 25, 40]), x = 25
Output: [25, 25]
Input: root = build_tree([20, 10, 30, 5, 15, 25, 40]), x = 2
Output: [None, 5]
Constraints
0 <= number of nodes <= 3000- All values are distinct integers
- O(h) time
Goals
- Track the best candidate while descending one path
- Distinguish the floor (at most x) from the ceiling (at least x)