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
- 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.
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