LeetCode 270 - Closest Binary Search Tree Value

LeetCode Problem 270

Difficulty: 🟢 Easy
Topics: Binary Search, Tree, Depth-First Search, Binary Search Tree, Binary Tree

Solution

Problem Understanding

The problem gives us the root of a Binary Search Tree, abbreviated as BST, and a floating point target value. Our task is to return the integer value stored in the BST that is numerically closest to the target.

A Binary Search Tree has a very important property:

• Every node in the left subtree contains a smaller value than the current node.
• Every node in the right subtree contains a larger value than the current node.

This ordering property is the key observation that allows us to solve the problem efficiently.

The input consists of:

• root, the root node of the BST
• target, a floating point number that may or may not exist in the tree

The expected output is:

• The node value whose absolute difference from target is minimal
• If two values are equally close, we must return the smaller one

For example, if the target is 3.7 and the tree contains values 3 and 4, then 4 is closer because:

• |3.7 - 3| = 0.7
• |3.7 - 4| = 0.3

Therefore the answer is 4.

The constraints tell us several important things:

• The tree contains between 1 and 10^4 nodes
• Node values can be very large, up to 10^9
• The target may even be outside the range of all node values

Since the tree can contain up to ten thousand nodes, a linear traversal is acceptable, but the BST structure suggests we can do better than scanning every node.

Several edge cases are important:

• The tree may contain only one node
• The target may be smaller than every value in the BST
• The target may be larger than every value in the BST
• Two values may be equally close to the target, in which case we must return the smaller one
• The target may exactly match a node value

The problem guarantees that the tree is non-empty, so we never need to handle a null root as the entire input.

Approaches

Brute Force Approach

The simplest approach is to traverse the entire tree and compare every node value against the target.

During traversal, we keep track of:

• The currently closest value
• The smallest absolute difference seen so far

For every node:

1. Compute abs(node.val - target)
2. Compare it against the current best difference
3. Update the answer if this node is closer
4. If the difference is tied, choose the smaller value

This approach is correct because it examines every node in the tree, guaranteeing that the closest value will eventually be found.

However, this ignores the BST property entirely. Even though the tree is ordered, the brute-force solution still visits all nodes.

Optimal BST Approach

The BST property allows us to make smarter decisions.

At each node:

• If target < node.val, then any potentially closer values must be in the left subtree
• If target > node.val, then any potentially closer values must be in the right subtree

This means we can follow a single path down the tree instead of exploring every node.

While traversing, we continuously maintain the closest value encountered so far.

The key insight is that the BST ordering lets us discard half of the remaining search space at each step, similar to binary search on a sorted array.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(h) recursive or O(n) worst-case	Traverses every node
Optimal	O(h) average, O(n) worst-case	O(1) iterative	Uses BST ordering to skip subtrees

Here:

• n is the number of nodes
• h is the height of the tree

In a balanced BST, h = log n, making the optimal solution very efficient.

Algorithm Walkthrough

1. Initialize a variable called closest with the root value.

We need some initial candidate answer. Since the tree is guaranteed to be non-empty, the root value is a safe starting point. 2. Start traversing from the root node.

We use a pointer called current to walk through the BST iteratively. 3. At each node, compare its value with the current best answer.

We compute:

abs(current.val - target)

and compare it against:

abs(closest - target)

If the current node is closer, we update closest.

If both distances are equal, we choose the smaller value because the problem explicitly requires that tie-breaking rule. 4. Decide which subtree to explore next.

The BST property tells us where better candidates could exist.

• If target < current.val, move left
• If target > current.val, move right
• If they are equal, we can immediately return because no value can be closer than an exact match

5. Continue until the traversal reaches a null node.

Once current becomes None or nil, we have exhausted the only relevant search path. 6. Return the stored closest value.

Why it works

The algorithm works because a BST is ordered. At every node, we know that one entire subtree cannot contain values that move closer toward the target.

If the target is smaller than the current value, then every value in the right subtree is even larger, making them less promising. Similarly, if the target is larger, the left subtree becomes less useful.

By always moving toward the side where closer values could exist, we efficiently search only the relevant path while continuously maintaining the best candidate encountered so far.

Python Solution

# 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

from typing import Optional

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

        while current:
            current_diff = abs(current.val - target)
            closest_diff = abs(closest - target)

            if (
                current_diff < closest_diff
                or (
                    current_diff == closest_diff
                    and current.val < closest
                )
            ):
                closest = current.val

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

        return closest

The implementation starts by storing the root value as the current best candidate. Since the tree is guaranteed to contain at least one node, this initialization is always valid.

The while current: loop walks through the BST iteratively. This avoids recursion and keeps the space complexity constant.

Inside the loop, the code computes the distance between the current node and the target, then compares it with the best distance seen so far.

The update condition handles two cases:

• The current node is strictly closer
• The current node is equally close but smaller, satisfying the tie-breaking requirement

After updating the candidate answer if necessary, the traversal direction is determined using BST ordering:

• Move left when the target is smaller
• Move right when the target is larger
• Return immediately on an exact match

The loop ends once the traversal falls off the tree, and the best stored value is returned.

Go Solution

import "math"

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func closestValue(root *TreeNode, target float64) int {
    closest := root.Val
    current := root

    for current != nil {
        currentDiff := math.Abs(float64(current.Val) - target)
        closestDiff := math.Abs(float64(closest) - target)

        if currentDiff < closestDiff ||
            (currentDiff == closestDiff && current.Val < closest) {
            closest = current.Val
        }

        if target < float64(current.Val) {
            current = current.Left
        } else if target > float64(current.Val) {
            current = current.Right
        } else {
            return current.Val
        }
    }

    return closest
}

The Go implementation follows the same logic as the Python solution.

One important difference is that Go requires explicit type conversion between integers and floating point values. Since target is a float64, node values must be converted before subtraction and comparison.

Go also uses nil instead of None for null pointers.

The iterative traversal avoids recursion, so no additional stack space is required beyond a few local variables.

Worked Examples

Example 1

Input:

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

BST structure:

       4
      / \
     2   5
    / \
   1   3

Traversal process:

Step	Current Node	Closest Before	Current Difference	Closest Difference	Updated Closest	Next Move
1	4	4	0.285714	0.285714	4	Move left
2	2	4	1.714286	0.285714	4	Move right
3	3	4	0.714286	0.285714	4	Move right
4	nil	4	-	-	4	Stop

Final answer:

4

Example 2

Input:

root = [1]
target = 4.428571

Traversal process:

Step	Current Node	Closest Before	Current Difference	Closest Difference	Updated Closest	Next Move
1	1	1	3.428571	3.428571	1	Move right
2	nil	1	-	-	1	Stop

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(h) average, O(n) worst-case	Traverses one BST path
Space	O(1)	Uses iterative traversal

The algorithm only follows a single path from the root toward a leaf. In a balanced BST, the height is logarithmic, so the runtime becomes O(log n).

In the worst case, the BST may be completely skewed like a linked list, making the height equal to n. In that case, the runtime degrades to O(n).

The implementation is iterative and stores only a few variables, so the auxiliary space usage remains constant.

Test Cases

# Helper TreeNode class for testing
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, target):
        closest = root.val
        current = root

        while current:
            current_diff = abs(current.val - target)
            closest_diff = abs(closest - target)

            if (
                current_diff < closest_diff
                or (
                    current_diff == closest_diff
                    and current.val < closest
                )
            ):
                closest = current.val

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

        return closest

solver = Solution()

# Example 1
root1 = TreeNode(4,
    TreeNode(2,
        TreeNode(1),
        TreeNode(3)),
    TreeNode(5))
assert solver.closestValue(root1, 3.714286) == 4  # standard example

# Example 2
root2 = TreeNode(1)
assert solver.closestValue(root2, 4.428571) == 1  # single node tree

# Exact match
root3 = TreeNode(4,
    TreeNode(2),
    TreeNode(6))
assert solver.closestValue(root3, 6.0) == 6  # exact target exists

# Target smaller than all nodes
root4 = TreeNode(10,
    TreeNode(5),
    TreeNode(15))
assert solver.closestValue(root4, -100.0) == 5  # minimum node closest

# Target larger than all nodes
root5 = TreeNode(10,
    TreeNode(5),
    TreeNode(15))
assert solver.closestValue(root5, 100.0) == 15  # maximum node closest

# Tie case, smaller value should win
root6 = TreeNode(4,
    TreeNode(2),
    TreeNode(6))
assert solver.closestValue(root6, 5.0) == 4  # equal distance between 4 and 6

# Left-skewed tree
root7 = TreeNode(5,
    TreeNode(4,
        TreeNode(3,
            TreeNode(2,
                TreeNode(1)))))
assert solver.closestValue(root7, 2.8) == 3  # skewed structure

# Right-skewed tree
root8 = TreeNode(1,
    None,
    TreeNode(2,
        None,
        TreeNode(3,
            None,
            TreeNode(4))))
assert solver.closestValue(root8, 3.6) == 4  # skewed structure

# Large values
root9 = TreeNode(1000000000,
    TreeNode(500000000),
    TreeNode(1500000000))
assert solver.closestValue(root9, 999999999.2) == 1000000000  # large integers

Test	Why
Standard balanced BST example	Verifies normal traversal behavior
Single node tree	Confirms minimal input handling
Exact target match	Ensures immediate return correctness
Target smaller than all nodes	Tests left boundary behavior
Target larger than all nodes	Tests right boundary behavior
Equal distance tie	Validates smaller-value tie-breaking rule
Left-skewed tree	Tests worst-case traversal shape
Right-skewed tree	Tests opposite skew direction
Large integer values	Ensures numeric comparisons remain correct

Edge Cases

One important edge case occurs when the tree contains only a single node. A careless implementation might assume the existence of children and attempt invalid traversal operations. In this implementation, the algorithm safely initializes closest with the root value and simply exits once traversal reaches None or nil.

Another critical edge case is when the target lies outside the range of all values in the BST. For example, the target may be much smaller than the minimum node value or much larger than the maximum node value. In these situations, the traversal naturally continues toward the extreme edge of the tree, and the closest boundary value is retained as the answer.

The tie-breaking rule is also easy to mishandle. If two values are equally close to the target, the problem requires returning the smaller value. A naive implementation that updates only on strictly smaller distance may incorrectly return the larger value depending on traversal order. This solution explicitly checks for equal differences and prefers the smaller integer.

A final edge case involves highly unbalanced trees. A BST can degenerate into a linked list, producing height n instead of log n. Recursive implementations may risk stack overflow in some environments. The iterative approach used here avoids recursion entirely and handles skewed trees safely.