Show problems as
Classic problem #272HardTwo PointersStackTreeDepth-First SearchBinary Search TreeHeap (Priority Queue)Binary Tree

Closest Binary Search Tree Value II

Real-world version: K Nearest Meter Readings
Tracked in this browser only
Read Closest Binary Search Tree Value II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A water utility files every meter reading it has ever taken into a binary search tree keyed by the reading itself: for any filed reading, everything in the branch to its left is smaller and everything in the branch to its right is larger. No two filed readings are the same.

The tree arrives as readings, a level-order listing. Its first entry is the reading at the top of the tree. After that, the listing gives the left branch then the right branch of each reading already listed, in the order those readings appear, writing null where a branch is empty. Slots below a null are never written down, and the trailing run of null entries is left off.

An auditor supplies target, a figure that need not be a whole number and may fall outside the range of the filed readings, and asks for the k readings nearest to it. Rank the filed readings by the size of the gap |reading - target|, smallest gap first; when two readings sit at exactly the same gap, the smaller reading ranks first. Take the first k readings of that ranking.

Return those k readings in ascending order. You are told that k never exceeds the number of filed readings.

Examples

Example 1

Input
readings = [20, 9, 35, 4, 14, 27, 41], target = 15.0, k = 3
Output
[9, 14, 20]

The filed readings are 4, 9, 14, 20, 27, 35 and 41, with gaps to 15 of 11, 6, 1, 5, 12, 20 and 26. The three smallest gaps belong to 14, 20 and 9, which come back in ascending order.

Example 2

Input
readings = [50, 40, null, 30, null, 20, null, 10], target = 25.0, k = 3
Output
[10, 20, 30]

Gaps to 25 are 25, 15, 5, 5 and 15 for readings 50, 40, 30, 20 and 10. Readings 20 and 30 take the first two places at a gap of 5, and the third place is contested at a gap of 15 by 10 and 40, where the smaller reading 10 ranks first.

Example 3

Input
readings = [10, null, 20, null, 30, null, 40], target = 35.0, k = 1
Output
[30]

Readings 30 and 40 both sit 5 away from 35, and the smaller of two equally close readings ranks first, so the single answer is 30.

Constraints

  • The number of readings filed in the tree is n.
  • 1 <= k <= n <= 10^4
  • 1 <= readings.length <= 2 * 10^4
  • 0 <= readings[i] <= 10^9
  • -10^9 <= target <= 10^9
  • An entry of readings that is null marks an empty branch rather than a reading.
  • readings[0] is never null, and no reading appears twice.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def nearest_readings(readings: list[int | None], target: float, k: int) -> list[int]:
Java
public List<Integer> nearestReadings(Integer[] readings, double target, int k)

More on the same topics