Show problems as
Classic problem #270EasyBinary SearchTreeDepth-First SearchBinary Search TreeBinary Tree

Closest Binary Search Tree Value

Real-world version: The Reading Nearest a Target
Tracked in this browser only
Read Closest Binary Search Tree Value on LeetCode(opens in a new tab)

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

Learn the pattern firstTraversal & Search · Binary Trees & BST, animated step by step

A gauge tree is given as the flat list rig. It hangs from a single top joint, every joint carries at most two joints below it in a first and a second slot, and either slot may be empty. Every reading in the first slot and below is smaller than the joint's own, and every reading in the second slot and below is larger.

A flat list is read level by level: its first entry is the top joint's reading, and reading left to right, every entry that is not null claims the next two unused positions as its first and second slot in that order, while null marks an empty slot and claims no positions of its own.

Return the reading on the rig closest to target. Where two readings are equally close, return the smaller one.

Examples

Example 1

Input
rig = [8, 4, 12, 2, 6, 10, 14], target = 7.0
Output
6

The readings 6 and 8 both sit one away from the target, and the smaller of the two is the answer.

Example 2

Input
rig = [5], target = 100.0
Output
5

There is only one reading on the rig, so it is the closest by default.

Example 3

Input
rig = [2, 1, 3], target = 2.5
Output
2

Both 2 and 3 sit half a unit from the target, so the smaller wins.

Constraints

  • 1 <= rig.length <= 30000
  • The rig holds between 1 and 10^4 joints.
  • 0 <= rig[i] <= 10^9
  • -10^9 <= target <= 10^9
  • The first entry of the list is not null.

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 closest_value(rig: list, target: float) -> int:
Java
public int closestValue(Integer[] rig, double target)

More on the same topics