270. Closest Binary Search Tree Value

This problem is common in MAANG-style interviews because it checks whether you can use a data structure’s ordering (BST invariants) to prune search, reason about comparisons with real numbers, and implement a precise tie-breaker condition instead of brute-forcing all nodes.

Problem statement

You’re given the root of a Binary Search Tree (BST) and a real number target. Return the value in the BST that is closest to the target. If there is more than one answer, print the smallest.

Constraints:

• The number of nodes in the tree is in the range [1, 10⁴].
• 0 <= Node.val <= 10⁹
• -10⁹ <= target <= 10⁹

Examples

1 / 5

Optimized approach using Binary Search Tree property

We do not need to scan the entire tree to find the value closest to the target. The key reason is the binary search tree property: values in the left subtree are smaller than the current node, and values in the right subtree are larger. This lets us decide which direction can still contain a better answer.

If the target is smaller than the current node’s value, then any value closer to the target must be in the left subtree, because every value in the right subtree is even larger and will generally be farther from a smaller target. Similarly, if the target is greater than or equal to the current node’s value, then any value closer to the target must be in the right subtree, because every value in the left subtree is smaller and will generally be farther from a larger target.

So the algorithm is a guided walk down one root-to-leaf path: at each node, update the best candidate if this node is closer to the target than the current best. If two values are equally close, apply a consistent tie-break rule, return the smaller value. This keeps the search efficient while still guaranteeing correctness.

Step-by-step algorithm

Here are the algorithm steps of the solution:

1. Initialize closest with the root node’s value.
2. While root is not None:
   1. Compare current.data with closest:
      1. If current.data is closer to target than closest, update closest.
      2. If both are equally close, keep the smaller value.
   2. Move in the BST based on the target:
      1. If target < current.data, set current = current.left.
      2. Otherwise, set current = current.right.
3. When the entire tree is traversed, return closest.

Take a look at the illustration below to understand the solution more clearly.

Code implementation in Python

Now, let’s look at the Python code for the optimized solution discussed above.

from queue import Queue
from collections import deque

def closestValue(root, target):
    # Initialize the closest value found as the root's data
    closest = root.data
    
    # Traverse the tree while nodes exist
    while root:
        # Update closest: prioritize smaller distance, then smaller value
        closest = min(root.data, closest, key=lambda x: (abs(target - x), x))
        
        # Check if the target is smaller than current node
        if target < root.data:
            # Move to the left subtree
            root = root.left
        # Otherwise, the target is larger or equal
        else:
            # Move to the right subtree
            root = root.right
            
    # Return the final closest value found
    return closest

# ----------------------------------------------------------------------------------------------------------------------------------
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        
class BinaryTree:
    def __init__(self, nodes):
        self.root = self.createBinaryTree(nodes)

    def createBinaryTree(self, nodes):
        if len(nodes) == 0:
            return None

        # Create the root node of the binary tree
        root = TreeNode(nodes[0].data)

        # Create a queue and add the root node to it
        queue = Queue()
        queue.put(root)

        # Start iterating over the list of nodes starting from the second node
        i = 1
        while i < len(nodes):
            curr = queue.get()

            # Assign left child
            if nodes[i] is not None:
                curr.left = TreeNode(nodes[i].data)
                queue.put(curr.left)
            i += 1

            # Assign right child
            if i < len(nodes) and nodes[i] is not None:
                curr.right = TreeNode(nodes[i].data)
                queue.put(curr.right)
            i += 1

        return root

    def levelOrder(self):
        """Return tree values in level-order as a Python list."""
        if self.root is None:
            return []
    
        result = []
        q = deque([self.root])
    
        while q:
            node = q.popleft()
            if node:
                result.append(node.data)
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
    
        return result
# ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
# driver code   
def main():
    # Example BSTs represented in Level Order
    input_trees = [
        [TreeNode(4), TreeNode(2), TreeNode(5), TreeNode(1), TreeNode(3)],
        [TreeNode(1), None, TreeNode(2)],
        [TreeNode(10), TreeNode(5), TreeNode(15), TreeNode(2), TreeNode(7)],
        [TreeNode(4), TreeNode(2), TreeNode(5), TreeNode(1), TreeNode(3)],
        [TreeNode(100), TreeNode(50), TreeNode(200), TreeNode(25), TreeNode(75), TreeNode(150), TreeNode(300)],
        [TreeNode(50), TreeNode(30), TreeNode(70), TreeNode(20), TreeNode(40), TreeNode(60), TreeNode(80)]
    ]
    
    input_targets = [3.714286, 3.428571, 12.0, 2.5, 120.0, 44.4]

    for i in range(len(input_trees)):
        tree = BinaryTree(input_trees[i])
        target = input_targets[i]
        
        print(i+1, ".\tBinary tree: ", tree.levelOrder(), sep="")
        print("\tTarget value: ", target)
        
        result = closestValue(tree.root, target)
        
        print("\n\tClosest value: ", result, sep="")
        print("-" * 75)

if __name__ == "__main__":
    main()

Time complexity

The time complexity for this solution is O(H), where H is the height of the tree. As we are using the properties of a Binary Search Tree, we do not need to visit every node; instead, we follow a single path from the root down to a leaf.

Space complexity

The space complexity for this solution is constant, O(1) because the algorithm is iterative rather than recursive, it does not use a call stack. We only maintain a few variables to track our progress, so the amount of memory used remains the same regardless of how large the tree grows.

Common mistakes

To ensure a high-quality implementation, be mindful of these common pitfalls and technical nuances that candidates often encounter during interviews.

• Forgetting the tie-breaker: A common error is failing to return the smaller value when two nodes are equally close to the target.
• Ignoring the BST Property: Avoid using a full Tree Traversal (BFS/DFS) which takes O(N) time; use the binary search logic to achieve O(H) time.
• Recursive space overhead: Using recursion adds O(H) to the space complexity due to the call stack; the iterative approach is superior as it uses O(1) space.
• Early exit opportunity: If you encounter a node value exactly equal to the target, return it immediately to save unnecessary iterations.
• Initial closest value: Do not initialize your tracking variable with 0 or a large constant; always initialize it with the root value to ensure it is a valid node from the start.
• Balanced vs. skewed Trees: In interviews, always clarify that while the average time complexity is O(log N), it degrades to O(N) if the tree is skewed (like a linked list).