Closest Element in a BST

Closest Element in a BST is a classic warm-up for thinking with the binary-search-tree invariant. Instead of scanning every node, you let the tree's order steer you straight toward the target — visiting at most one node per level.

The slow way first

The obvious idea: walk every node, compute |node.val - target| for each, and keep the minimum. That works for any tree and is O(n) — you touch all n nodes.

But this is a BST, and we are throwing away its biggest gift: order. At any node, every value to the left is smaller and every value to the right is larger. So once we compare with a node, we already know which side the closer value must be on. There is no reason to ever look at the other side.

The idea: step toward the target

Keep a running closest candidate. Start at the root and repeat: compare the current node, update closest if this node is nearer, then move left if the target is smaller and right if it is larger. When you walk off the bottom (a child is None), stop.

The key insight: each comparison eliminates an entire subtree, so the path length is the tree height, not the node count. On a balanced BST that is O(log n).

Walk through it

Step through the animation with target = 9. The node pointer rides the current node. We start at root 8 (diff 1, our best). 9 > 8, so we turn right to 12 (diff 3, worse — keep 8). 9 < 12, so we turn left to 10 (diff 1, a tie — we keep 8). 9 < 10, but 10 has no left child, so the loop ends. Answer: 8, after visiting only 3 of the 7 nodes.

Pseudocode

closest = root.val
node = root
while node is not None:
    if |node.val - target| < |closest - target|:
        closest = node.val
    if target > node.val:
        node = node.right        # closer value can only be larger
    else:
        node = node.left         # closer value can only be smaller
return closest

The Python solution

def closest_value(root, target):
    closest = root.val
    node = root
    while node:
        if abs(node.val - target) < abs(closest - target):
            closest = node.val
        if target > node.val:
            node = node.right
        else:
            node = node.left
    return closest

• closest starts at the root value so we always have a candidate to compare against.
• The while node loop walks a single root-to-leaf path; each turn drops the half of the tree we ruled out.
• Line 5 is the candidate test — we only replace closest on a strictly smaller difference, so ties keep the earlier value.
• Lines 7–10 are the steering: target > node.val means the closer value is to the right, otherwise left.
• When node becomes None, the loop ends and we return the best value found.

Complexity

We use only O(1) extra space — a couple of variables, no recursion stack (the loop is iterative). The runtime is O(height): great on a balanced tree, and no worse than the brute force on a degenerate one.

When this pattern shows up

Practice