LeetCode 270: Closest Binary Search Tree Value

Problem Restatement

We are given the root of a binary search tree and a target value.

The target can be a floating-point number.

We need to return the value in the BST that is closest to the target.

If multiple values are equally close, return the smaller value. The tree contains between 1 and 10^4 nodes, node values are in [0, 10^9], and the target is in [-10^9, 10^9].

Input and Output

Example function shape:

def closestValue(root: Optional[TreeNode], target: float) -> int:
    ...

Examples

Example 1:

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

Tree:

    4
   / \
  2   5
 / \
1   3

Compare distances:

The closest value is:

4

Answer:

4

Example 2:

root = [1]
target = 4.428571

There is only one node.

Answer:

1

First Thought: Visit Every Node

A direct solution is to traverse the whole tree.

For every node:

1. Compute the absolute difference from target.
2. Keep the value with the smallest difference.
3. Return the best value after visiting all nodes.

This works for any binary tree.

class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        closest = root.val

        def dfs(node: Optional[TreeNode]) -> None:
            nonlocal closest

            if node is None:
                return

            if abs(node.val - target) < abs(closest - target):
                closest = node.val
            elif abs(node.val - target) == abs(closest - target):
                closest = min(closest, node.val)

            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return closest

This is correct, but it does not use the BST ordering.

Problem With Full Traversal

A full DFS visits every node.

So the time complexity is:

O(n)

The BST property gives us a better direction.

If the target is smaller than the current node value, closer values may exist on the left.

If the target is larger than the current node value, closer values may exist on the right.

So we can walk down one path instead of traversing the whole tree.

Key Insight

At every node, the current node is a candidate answer.

After checking it:

• If target < node.val, move left.
• If target > node.val, move right.
• If target == node.val, return immediately.

This works because a BST is ordered.

For example, at node 4:

target = 3.714286

Since the target is smaller than 4, the only subtree that might contain a closer value is the left subtree.

The right subtree contains values larger than 4, so those values are even farther from a target below 4.

Algorithm

1. Set closest = root.val.
2. Start at node = root.
3. While node exists:
   • If node.val is closer to target, update closest.
   • If the distance ties, keep the smaller value.
   • If target < node.val, move to node.left.
   • Otherwise, move to node.right.
4. Return closest.

Walkthrough

Use:

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

Start:

closest = 4
node = 4

Distance:

abs(4 - 3.714286) = 0.285714

Move left because:

3.714286 < 4

Now:

node = 2

Distance:

abs(2 - 3.714286) = 1.714286

2 is farther than 4, so keep closest = 4.

Move right because:

3.714286 > 2

Now:

node = 3

Distance:

abs(3 - 3.714286) = 0.714286

3 is farther than 4, so keep closest = 4.

Move right because:

3.714286 > 3

There is no right child.

Return:

4

Correctness

The algorithm keeps closest as the best value seen so far on the search path.

At every visited node, it compares that node against the current best answer. Therefore closest is always the closest value among all visited nodes.

The BST property lets the algorithm choose one direction. If target is smaller than node.val, all values in the right subtree are greater than node.val, so they cannot be closer than node.val itself. Since node.val has already been considered, skipping the right subtree is safe. The symmetric argument applies when target is larger than node.val.

Thus every skipped subtree cannot contain a better answer than a value already considered on the path.

When traversal ends, closest is the closest value in the BST.

The tie rule is handled by choosing the smaller value when distances are equal.

Complexity

Let h be the height of the tree.

For a balanced BST, h = O(log n).

For a skewed BST, h = O(n).

Implementation

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        closest = root.val
        node = root

        while node is not None:
            current_diff = abs(node.val - target)
            closest_diff = abs(closest - target)

            if current_diff < closest_diff:
                closest = node.val
            elif current_diff == closest_diff and node.val < closest:
                closest = node.val

            if target < node.val:
                node = node.left
            elif target > node.val:
                node = node.right
            else:
                return node.val

        return closest

Code Explanation

Initialize the answer with the root value:

closest = root.val

The tree has at least one node, so this is safe.

At every node, compare the current value with the best value so far:

current_diff = abs(node.val - target)
closest_diff = abs(closest - target)

If the current node is closer, update:

closest = node.val

For a tie, use the smaller value:

elif current_diff == closest_diff and node.val < closest:
    closest = node.val

Then move in the only useful BST direction:

if target < node.val:
    node = node.left
elif target > node.val:
    node = node.right
else:
    return node.val

If we find the exact target, no value can be closer, so we return immediately.

Testing

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    root = TreeNode(
        4,
        TreeNode(2, TreeNode(1), TreeNode(3)),
        TreeNode(5),
    )
    assert s.closestValue(root, 3.714286) == 4
    assert s.closestValue(root, 3.2) == 3
    assert s.closestValue(root, 4.0) == 4

    root = TreeNode(1)
    assert s.closestValue(root, 4.428571) == 1

    root = TreeNode(2, TreeNode(1), TreeNode(3))
    assert s.closestValue(root, 2.5) == 2

    root = TreeNode(10, TreeNode(5), TreeNode(15))
    assert s.closestValue(root, -100.0) == 5
    assert s.closestValue(root, 100.0) == 15

    print("all tests passed")

run_tests()

Test meaning: