Closest Binary Search Tree Value

easy tree bst binary search

Problem

Given the root of a non-empty BST and a target value, return the value in the BST closest to the target.

Inputroot = [4,2,5,1,3], target = 3.714

Output4

Walk: 4 → 5 (3.71 < 5? no, go to right → done at 5 missing? Best closest is 4).

BST (level-order, 'n' for null)

target

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

function closestValue(root, target) {
  let best = root.val, node = root;
  while (node) {
    if (Math.abs(node.val - target) < Math.abs(best - target)) best = node.val;
    node = target < node.val ? node.left : node.right;
  }
  return best;
}

class Solution {
    public int closestValue(TreeNode root, double target) {
        int best = root.val; TreeNode node = root;
        while (node != null) {
            if (Math.abs(node.val - target) < Math.abs(best - target)) best = node.val;
            node = target < node.val ? node.left : node.right;
        }
        return best;
    }
}

int closestValue(TreeNode* root, double target) {
    int best = root->val; auto* node = root;
    while (node) {
        if (abs(node->val - target) < abs(best - target)) best = node->val;
        node = target < node->val ? node->left : node->right;
    }
    return best;
}

Explanation

We are looking for the single BST value closest to a target. Instead of checking every node, we use the BST ordering to walk a single path from the root downward, just like a binary search.

We keep a variable best for the closest value seen so far, starting at the root. At each node, if its value is nearer to the target than best, we update best.

Then we decide where to go next. If target < node.val the closer values must be on the left, otherwise on the right. We keep stepping down until we fall off the tree.

Example: BST [4, 2, 5, 1, 3], target = 3.714. Start at 4 (best = 4). Since 3.714 < 4 go left to 2 (4 is still closer, best stays 4). Since 3.714 > 2 go right to 3 (distance 0.714 vs 0.286, so 4 stays best). No further children, so the answer is 4.

This is fast because we only follow one root-to-leaf path instead of scanning the whole tree.

Time: O(h) Space: O(1)