DSA Factory
Free lessonsBinary search trees · Stage 0 · Search and insert · Step 4

Closest value in BST

Track the closest node seen so far while navigating left or right toward the target. About 9 minutes.

Tracking the closest value

The target might not exist in the BST, but some node will be closest to it, like the shop nearest your home even if none is on your street. Start by assuming the root is the closest.

At every node you visit, check whether its distance to the target is smaller than your best distance so far. If it is, it becomes the new closest.

Start with the root: it is the first candidate.
Distance: compare how far each node is from the target, with no sign.
root = [4, 2, 5, 1, 3], target = 3
12345
gap
1
closest
4

4 is 1 away from 3. Best so far. 3 < 4, so anything closer must be on the left.

Move 1 of 3

Which direction to move?

Compare the target with the current node. If the target is smaller, you want a smaller value, so move left. If the target is larger, move right. If they are equal, the distance is 0 and you can stop immediately.

This is the same steering as plain search, but with a note-taking step at each stop.

Target smaller: step left; the right side can only be further away.
Target larger: step right; the left side can only be further away.
In code
closest = root.val
curr = root
while curr:
    d = abs(curr.val - target)
    best = abs(closest - target)
    if d < best:
        closest = curr.val
    elif d == best and curr.val < closest:
        closest = curr.val
    if target < curr.val:
        curr = curr.left
    elif target > curr.val:
        curr = curr.right
    else:
        break
return closest
Quick check

Standing on node 20 with target 14, where should you move next?

  1. ALeft child
  2. BRight child
  3. CStop immediately
Show the answer

Left child. 14 < 20, so numbers closer to 14 must be smaller than 20 (in the left subtree).

Your problem

Closest value in BST

Given the root of a non-empty binary search tree (BST) and an integer target, return the value in the BST that is closest to target. If there is a tie, return the smaller value.

Example
root = [4, 2, 5, 1, 3], target = 3 → 3

1 ≤ number of nodes ≤ 10,000 · -1,000,000 ≤ node.val, target ≤ 1,000,000

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding