EasyBinary Search TreeTreeDepth-First SearchBinary Tree

Closest Binary Search Tree Value

1 approach, code in every language

You are given the root of a binary search tree (BST) and a floating-point number target.

Return the value stored in the tree that is closest to target, where closeness is measured by absolute difference. If two different node values are equally close to the target, return the smaller of the two values.

Example 1

Input: root = [4,2,5,1,3], target = 3.714286

Output: 4

Among the values, 4 is nearest to 3.714286 (distance about 0.286), closer than 3 (distance about 0.714).

Example 2

Input: root = [1], target = 4.428571

Output: 1

The tree holds only the value 1, so it is trivially the closest to the target.

Constraints

The number of nodes in the tree is in the range [1, 10^4].
0 <= Node.val <= 10^9
-10^9 <= target <= 10^9

Guided BST Descent

Descend the tree using BST comparisons, updating the best candidate whenever a closer (or equal-but-smaller) value appears.

Loading animation…

Intuition

Because the tree is a BST, the target's comparison with a node tells us which side could hold something even closer. Track the closest value seen so far, initialized to the root's value, and refine it as we descend. At each node, compute its distance to the target and adopt it as the new best when it is strictly nearer, or when it ties the current best but has a smaller value (honoring the tie-break rule). Then, if the target is less than the current node's value the only chance to improve lies to the left, otherwise to the right. Moving one step at a time toward the target keeps the search on the height of the tree rather than the whole tree.

Algorithm walkthrough

1Initialize closest to the root's value as a starting candidate.
2While the current node is non-null, measure |node.val - target| and compare it to |closest - target|.
3Update closest to node.val when the new distance is strictly smaller, or equal but node.val is smaller (tie-break).
4If target is less than node.val, move to the left child; otherwise move to the right child.
5Repeat until the walk runs off the tree (current node becomes null).
6Return closest, the nearest value encountered along the path.

Implementation

class Solution:
    def closestValue(self, root: 'TreeNode', target: float) -> int:
        closest = root.val
        while root is not None:
            diff = abs(root.val - target)
            best = abs(closest - target)
            if diff < best or (diff == best and root.val < closest):
                closest = root.val
            if target < root.val:
                root = root.left
            else:
                root = root.right
        return closest

Time

O(h)

Space

O(1)

The descent visits one node per level, giving O(h) time (O(log n) balanced, O(n) skewed) and constant extra space since only the running closest value is stored.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

The Reading Nearest a Target is our own problem on the technique behind Closest Binary Search Tree Value: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free