NUHMAN.com

Introduction

LeetCode 270: Closest Binary Search Tree Value is a simple yet elegant tree problem. Given a target number and a Binary Search Tree (BST), your task is to find the value in the BST that is closest to the target.

This is a classic greedy + binary search tree traversal problem that tests your understanding of BST properties.

Problem Statement

Given the root of a Binary Search Tree and a target value, return the value in the BST that is closest to the target.

Examples

python

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

Input: root = [1], target = 4.428571
Output: 1

✅ Step-by-Step Solution in Python

🧠 Key Insight

Since it's a BST, we can leverage its property:

• Left child < node < right child
• This allows us to move left or right depending on the target and current value

🔁 Step 1: Traverse BST Greedily

• Keep track of the closest value seen so far
• At each node:
• If target < node.val → go left
• If target > node.val → go right
• Update the closest value if current node is closer

✅ Python Code (Iterative)

python

def closestValue(root, target):
    closest = root.val
    while root:
        # Update closest if current node is closer
        if abs(root.val - target) < abs(closest - target):
            closest = root.val
        
        # Decide direction
        if target < root.val:
            root = root.left
        else:
            root = root.right
            
    return closest

✅ Python Code (Recursive)

python

def closestValue(root, target):
    def helper(node, closest):
        if not node:
            return closest
        if abs(node.val - target) < abs(closest - target):
            closest = node.val
        if target < node.val:
            return helper(node.left, closest)
        else:
            return helper(node.right, closest)
    return helper(root, root.val)

🧪 Dry Run

Input: root = [4, 2, 5, 1, 3], target = 3.714

• Start at 4 → closest = 4
• 3.714 < 4 → go left to 2
• 2 is further → keep closest = 4
• 3.714 > 2 → go right to 3
• 3 is closer → update closest = 3
• 3.714 > 3 → go right (None) → Done

✅ Closest value = 4

⏱️ Time and Space Complexity

• Time Complexity: O(h)
• where h = height of tree
• O(log n) for balanced BST
• O(n) for skewed BST
• Space Complexity:
• O(1) for iterative
• O(h) for recursive (stack space)

📌 Edge Cases

• Tree has only 1 node → return that node
• Target less than all node values → return the smallest
• Target greater than all node values → return the largest

✅ Conclusion

LeetCode 270: Closest Binary Search Tree Value is a perfect example of optimizing search using BST structure.

You learned:

• How to traverse a BST greedily
• When to update the closest value
• Both iterative and recursive solutions