A lab stores calibration values in a non-empty binary search tree with distinct integer values. Given a measurement target (an integer or a float), return the stored value closest to it. If two values are equally close, return the smaller one.
Examples
12
/ \
7 18
/ \ / \
3 9 15 22
\
5
Input: root = build_tree([12, 7, 18, 3, 9, 15, 22, None, 5]), target = 10.4
Output: 9
Input: root = build_tree([12, 7, 18, 3, 9, 15, 22, None, 5]), target = 16.5
Output: 15 (15 and 18 are both 1.5 away; the smaller wins)
Constraints
1 <= number of nodes <= 3000- All values are distinct integers
- O(h) time
Goals
- Compare distances while walking a single path
- Apply a deterministic tie-break