The k nearest values
Find the k values of a search tree that are closest to a target, by reading the values in order and shrinking a window from whichever end is farther away. About 20 minutes.
A block in sorted order
Read the tree's values in order. They are sorted. The k values closest to a target form one unbroken block of this sorted list, because if a value is in the block, every value between it and the target is even closer.
So you do not need to sort by distance. You only need to find the right block of length k.
lo, hi = 0, len(vals) - 1 width = hi - lo + 1
The window holds all six. The ends 2 and 15 are 7 and 6 away from 9. Drop the farther one, 2.
Drop the farther end
Start with a window over all the values. While the window holds more than k values, compare the two ends: the left end is the target minus the first value away, the right end is the last value minus the target away. Drop the end that is farther away.
If the two ends are the same distance away, drop the larger one, so the smaller value is kept. When k values remain, they are the answer, already in increasing order.
left_gap = target - vals[lo] right_gap = vals[hi] - target
The two ends of the window are the same distance from the target. Which is dropped?
- AThe larger one
- BThe smaller one
- CBoth
Show the answer
The larger one. The task keeps the smaller value on a tie.
Closest k values in a search tree
Given the root of a binary search tree with different values, an integer target and an integer k, return the k values in the tree that are closest to target, in increasing order. If two values are the same distance from target, the smaller one is considered closer. It is guaranteed that k does not exceed the number of nodes.
root = [4, 2, 5, 1, 3], target = 3, k = 2 → [2, 3]
1 ≤ k ≤ number of nodes ≤ 10,000 · -1,000,000 ≤ node.val, target ≤ 1,000,000