Closest BST Value

Problem

Given the root of a BST and a double target, return the integer value of the node closest to target.

Constraints

• 1 ≤ nodes ≤ 10⁴

Approach — Tree Traversal

This is a Tree Traversal problem. The idea: traverse the tree — DFS recursively, or BFS level by level — and combine the results from each subtree. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

class Solution:
    def closestValue(self, root, target):
        closest = root.val
        while root:
            if abs(root.val - target) < abs(closest - target) or                (abs(root.val - target) == abs(closest - target) and root.val < closest):
                closest = root.val
            root = root.left if target < root.val else root.right
        return closest

Java

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.