Domain 1EasyCORE

Closest Binary Search Tree Value

The problem asks us to find the value in a Binary Search Tree (BST) that is closest to a given target value. The inputs are the root of the BST and the target value. The output should be the node value in the BST that minimizes the absolute difference between itself and the target.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Binary Search#Tree

270. Closest Binary Search Tree Value

Model: qwen2.5-coder:14b
Topics: Binary Search,Tree
FAANG asked: 1
Acceptance rate: 50.3%


Problem Breakdown

The problem asks us to find the value in a Binary Search Tree (BST) that is closest to a given target value. The inputs are the root of the BST and the target value. The output should be the node value in the BST that minimizes the absolute difference between itself and the target.

Inputs:

  • root: The root node of the binary search tree.
  • target: A floating-point number representing the target value.

Outputs:

  • An integer value from the BST that is closest to the target.

Implicit Constraints or Edge Cases:

  • The BST can have up to 10,000 nodes.
  • Node values and the target can be as large as (10^9) in absolute terms.
  • The tree could be unbalanced, but it will always be a valid BST (i.e., left child < parent < right child).

Intuition

A brute-force approach would involve traversing all nodes in the BST to find the one with the minimum absolute difference from the target. This would result in a time complexity of (O(n)), where (n) is the number of nodes, which is acceptable given the constraints.

However, we can leverage the properties of a binary search tree to improve our approach. Since the left subtree contains values less than the root and the right subtree contains values greater than the root, we can make informed decisions about which subtree to explore next based on the target value. This leads us to a more efficient solution with (O(h)) time complexity, where (h) is the height of the tree.

Approach

  1. Initialize Variables: Start by initializing closest_val to the root’s value and min_diff to the absolute difference between the root’s value and the target.
  2. Traverse the Tree:
    • Begin at the root node.
    • At each node, update closest_val if the current node’s value is closer to the target than the previously recorded closest value.
    • Compare the target with the current node’s value:
      • If the target is less than the current node’s value, move to the left child (since all values in the right subtree are greater).
      • If the target is greater than or equal to the current node’s value, move to the right child.
    • Continue this process until you reach a leaf node (i.e., a node with no children).
  3. Return Result: Once traversal is complete, closest_val will hold the value in the BST that is closest to the target.

Complexity Analysis

  • Time Complexity: (O(h)), where (h) is the height of the tree. In the worst case (unbalanced tree), this could be (O(n)). However, for a balanced tree, it would be (O(\log n)).
  • Space Complexity: (O(1)) since we are using only a constant amount of extra space.

Solution

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

def closestValue(root: TreeNode, target: float) -> int:
    closest_val = root.val
    min_diff = abs(target - root.val)
    
    current = root
    while current:
        if abs(target - current.val) < min_diff:
            closest_val = current.val
            min_diff = abs(target - current.val)
        
        if target < current.val:
            current = current.left
        else:
            current = current.right
    
    return closest_val

Edge Cases Handled

  • Single Node Tree: If the tree has only one node, that node’s value is returned as it is the only candidate.
  • Target Value Greater than All Nodes: The algorithm will traverse to the rightmost node and return its value.
  • Target Value Less Than All Nodes: The algorithm will traverse to the leftmost node and return its value.
  • Balanced vs. Unbalanced Tree: The solution handles both cases efficiently, with time complexity depending on the height of the tree.

The provided solution is correct, efficient, and clear. It leverages the properties of a binary search tree to minimize unnecessary traversals, ensuring optimal performance.