Closest Binary Search Tree Value II

Closest Binary Search Tree Value II asks for the k values in a BST that sit nearest to a target. The trick is to remember that an in-order traversal of a BST is a sorted sequence, and that the closest values must hug the target from the left and right.

The slow way first

The obvious idea: do a full in-order traversal to get the sorted list, compute every distance to the target, sort by distance, and take the first k. That works but costs O(n log n) and touches all n nodes even when k is tiny.

The question to ask: the answer is a contiguous window in the sorted order, centered on the target — can I grow that window outward instead of scanning everything?

The idea: two iterators sweeping outward

Because in-order is sorted, the closest values fan out from the target. Build two iterators:

• a predecessor iterator that yields values < target in decreasing order (the largest one first),
• a successor iterator that yields values >= target in increasing order (the smallest one first).

Each round, look at the two frontier values and take whichever is closer to the target, then advance that side. Do this k times.

The key insight: the closest unseen value is always one of the two frontiers, so a simple greedy pick is correct.

Walk through it

Step through the animation. The two markers start at 3 (pred) and 4 (succ). Round 1: 4 is closer (0.3 vs 0.7), so take 4 and the successor advances to 5. Round 2: now 3 beats 5 (0.7 vs 1.3), so take 3. We have k = 2 values and stop: the answer is [4, 3].

Pseudocode

pred = iterator of values < target, decreasing
succ = iterator of values >= target, increasing
p = first pred value, s = first succ value
result = []
while result has fewer than k values:
    if succ is exhausted, or pred exists and |target - p| <= |s - target|:
        take p; advance pred
    else:
        take s; advance succ
return result

The Python solution

def closest_k(root, target, k):
    pred = predecessors(root, target)  # values < target, decreasing
    succ = successors(root, target)    # values >= target, increasing
    p, s = next(pred, None), next(succ, None)
    result = []
    while len(result) < k:
        if s is None or (p is not None and
                         target - p <= s - target):
            result.append(p); p = next(pred, None)
        else:
            result.append(s); s = next(succ, None)
    return result

• pred and succ are generators (built from iterative in-order walks with explicit stacks) that lazily yield the next nearer value on each side.
• p and s hold the current frontier value of each side; None means that side is exhausted.
• The while loop runs until we have collected k values.
• The if chooses the predecessor when the successor is gone, or when p is at least as close as s (target - p <= s - target, since p <= target <= s).
• Whichever side we take, we advance only that iterator with next(..., None).

Complexity

We only ever expand k steps outward from the target, plus the cost of seeding each iterator down one root-to-leaf path of height h. That is far cheaper than touching every node when k is small.

When this pattern shows up

Practice