1071EasyBinary SearchTreeDepth-First SearchBinary Search TreeBinary Tree

The Reading Nearest a Target

Tracked in this browser only

Trains the technique from

LeetCode 270Closest Binary Search Tree Value

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def closest_value(rig: list, target: float) -> int:

Java

public int closestValue(Integer[] rig, double target)

The intended approach

Time O(n) to read the list, then O(h) for the walk down a rig of depth h.Space O(n) for the slots.

The ordering means the search never has to look at both slots. Standing at a joint, compare its reading with the target: everything in one slot lies on one side of the reading and everything in the other slot on the other, so only the slot on the target's side can hold anything closer. So walk down from the top, keeping the best reading met so far. A reading is better when it is strictly closer, or when it is equally close and smaller, which is what settles a tie the way the answer asks. Then step into the first slot when the target is below the reading and into the second when above; landing exactly on the target ends the walk at once. Reading the flat list into slots takes one pass, and the walk itself goes no deeper than the rig hangs.

Pythonentry point: closest_value

def closest_value(rig, target):
    n = len(rig)
    left = {}
    right = {}
    level = [0]
    at = 1
    while level and at < n:
        nxt = []
        for owner in level:
            if at < n:
                if rig[at] is not None:
                    left[owner] = at
                    nxt.append(at)
                at += 1
            if at < n:
                if rig[at] is not None:
                    right[owner] = at
                    nxt.append(at)
                at += 1
        level = nxt
    best = rig[0]
    here = 0
    while here is not None:
        value = rig[here]
        gap = value - target if value > target else target - value
        keep = best - target if best > target else target - best
        if gap < keep or (gap == keep and value < best):
            best = value
        if value == target:
            break
        if target < value:
            here = left.get(here)
        else:
            here = right.get(here)
    return best

The obvious version

Ignore the ordering and look at every reading on the rig, keeping whichever is closest to the target and the smaller of two equally close ones. Costs every joint rather than one walk down.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_closest_value(rig, target):
    best = None
    for value in rig:
        if value is None:
            continue
        if best is None:
            best = value
            continue
        gap = value - target if value > target else target - value
        keep = best - target if best > target else target - best
        if gap < keep or (gap == keep and value < best):
            best = value
    return best

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in