We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Closest Binary Search Tree Value

Number: 270

Difficulty: Easy

Paid? Yes

Companies: Meta, Oracle, Microsoft, Google, Snap

Problem Description

Given the root of a binary search tree (BST) and a target value, the task is to return the value in the BST that is closest to the target. If there are multiple closest values (i.e. same absolute distance), return the smallest value among them.

Key Insights

  • BST property allows us to traverse the tree efficiently by comparing the target with node values.
  • We can iteratively traverse the tree, moving left if the target is smaller than the current node’s value and moving right if greater.
  • At each node, calculate the absolute difference between node's value and the target, and update the answer if the difference is smaller—or equal with a smaller candidate value.
  • This approach minimizes the search area by leveraging the inherent ordering in BSTs.

Space and Time Complexity

Time Complexity: O(h) on average, where h is the height of the tree (O(log n) for a balanced tree, and O(n) in the worst-case scenario for a skewed tree).
Space Complexity: O(1) for an iterative solution (or O(h) if using recursion due to the call stack).

Solution

We solve the problem by performing an iterative traversal of the BST. Starting at the root, we maintain a variable to store the value closest to the target. For every node encountered, we:

  • Compute the absolute difference between the node’s value and the target.
  • Update the stored closest value if the computed difference is less than the current smallest difference; if the difference is the same, choose the smaller node value.
  • Depending on whether the target is less than or greater than the current node's value, move to the left or right child accordingly. This approach efficiently defines a search path that is consistent with the properties of a BST.

Code Solutions

# Python solution for Closest Binary Search Tree Value

# 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: TreeNode, target: float) -> int:
        # Initialize the best value with the value of the root
        best_value = root.val
        
        # Traverse the BST iteratively
        current = root
        while current:
            # Calculate the difference between current node's value and target
            current_diff = abs(current.val - target)
            best_diff = abs(best_value - target)
            
            # Update best_value if a closer difference is found, or if equal and current value is smaller
            if current_diff < best_diff or (current_diff == best_diff and current.val < best_value):
                best_value = current.val
            
            # Decide the traversal direction based on the target comparison
            if target < current.val:
                current = current.left
            else:
                current = current.right
        
        return best_value
← Back to All Questions