518. Nearest Key
A thermostat stores the set-points it supports in a binary search tree. Given a requested temperature target, which may be fractional, the device must pick the supported set-point that is closest to it.
Return the key of the node in root whose absolute difference from target is smallest. If two keys are equally close to the target, return the smaller one. The tree always has at least one node, so an answer always exists, and the returned value is the integer key itself, not the distance.
Example 1
- Input:
- root = [9,4,14,2,6,11,17], target = 7.5
- Output:
- 6
- Explanation:
Keys 6 and 9 are both 1.5 away from 7.5, so the smaller key 6 is returned.
Example 2
- Input:
- root = [9,4,14,2,6,11,17], target = 12.25
- Output:
- 11
- Explanation:
Key 11 is 1.25 away from 12.25 and key 14 is 1.75 away, so 11 is closest.
Constraints
1 ≤ number of nodes ≤ 104
-1000 ≤ node key ≤ 1000, all keys distinct
-104 ≤ target ≤ 104, given as a multiple of 0.25
root is a valid binary search tree.
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)