Closest Neighbour in BST

Given the root of a binary search tree and an integer key, return the value in the BST that is closest to key — the one with the smallest absolute difference |value - key|. If two values tie, return the smaller one.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

The closest value lies on the search path toward the key.

Descend the BST, keeping the value with the smallest |value - key| so far.

Break ties toward the smaller value, and stop early on an exact match.

Common doubts

The ordering means any subtree you skip is entirely farther from the key than the boundary node you visited, so the best candidate is always on the path.

No — one comparison decides the direction, keeping it O(height).

When two values are equally close, the smaller one is returned.

Interview follow-ups

· What an interviewer asks next.

The closest neighbour is whichever of the floor and ceil of the key is nearer — this descent finds it in one pass.

Use an inorder walk (sorted) plus a two-pointer or heap around the key's position.

Fun facts

The closest neighbour is always either the floor or the ceil of the key — never anything else.
This is BST binary search with a 'best so far' accumulator, the same idea as nearest-value search on a sorted array.

Asked at

AmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: root = [8, 4, 12, 2, 6, 10, 14], key = 11
Output: 10
10 and 12 are both distance 1 from 11; the smaller (10) is returned.

Example 2

Input: root = [8, 4, 12, 2, 6, 10, 14], key = 6
Output: 6
6 is in the tree — distance 0.

Constraints

- The number of nodes is in the range [1, 10^5] - 1 <= Node.val <= 10^6 - root is a valid BST - 1 <= key <= 10^6

The closest value must lie on the search path for the key. As you descend the BST toward where key would sit, every node you pass is a candidate — and the ordering guarantees that the true closest neighbour is one of them. So walk down, keep the best candidate, and you're done in O(height) instead of scanning all nodes.

Prerequisites

Before you start

· Concepts used directly in the solution.

BST invariant. Left < node < right, at every node.

Best-candidate descent. Track the closest value seen while descending.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Definition

“Closest by what measure?”

Smallest absolute difference |value − key|.

“Ties?”

Return the smaller value.

The ideal opening — say it like this

I descend toward where the key would go, and every node on that path is a candidate for the closest value.

I keep the best difference as I go and stop at an exact match or when I fall off the tree.

Understand the problem

Worked example — BST [8, 4, 12, 2, 6, 10, 14], key = 11

8  -> diff 3, best 8
12 -> diff 1, best 12  (go left, since 11 < 12)
10 -> diff 1, tie with 12 -> smaller wins -> best 10
(null) -> closest = 10

Key observations

1Aha

The answer is on the search path

Ordering guarantees the closest value is one of the nodes you pass descending toward the key.

2Aha

Track the best difference

Update the candidate whenever a node is strictly closer, or equally close but smaller.

3Aha

O(height), not O(n)

No need to scan the whole tree — the descent visits O(height) nodes.

Brute force vs optimal

	Scan every node	BST descent
Idea	Check all values for the min difference	Descend toward key, track best on the path
Time	O(n)	O(height)
Space	O(height)	O(1)

Both find the same value; the descent uses the ordering to skip most of the tree. Full code is in the Approaches selector below.

Summary

Key takeaway

Descend toward the key, updating the closest candidate (ties → smaller). The closest neighbour is always on that path. O(height) time, O(1) space.

while node:
    update best with node.val
    if node.val == key: break
    node = node.left if key < node.val else node.right