Closest Binary Search Tree Value
Easy · Trees · Tree · Binary Search Tree · Binary Search
Problem
Given the root of a binary search tree and a real number target, return the value in the tree that is closest to target.
If two values are equally close, return the smaller one.
Examples
Input: root = [10,4,15,2,7], target = 6.4 Output: 7
7 is 0.6 away, closer than 4 or 10.
Input: root = [10,4,15,2,7], target = 12.5 Output: 10
10 and 15 are both 2.5 away, so the smaller one wins.
Input: root = [3], target = 100.0 Output: 3
The only value is the answer, however far away.
Constraints
- The number of nodes is in the range [1, 10^4]
- 0 <= Node.val <= 10^9
- -10^9 <= target <= 10^9
Approaches
- Baseline: visit every node — time O(n), space O(n)
Follow-up
For the k closest values, walk the tree in order with a window of size k (drop from the front while the new value is closer), or keep two stacks for the predecessors and successors of target and merge them: O(h + k) time.
Related problems
Start free on Cariara · Coding problems · System design studio
