LeetCode 270: Closest BST Value Solution in Python – A Step-by-Step Guide

Imagine you’re exploring a binary search tree (BST), where numbers are neatly arranged—smaller ones to the left, bigger ones to the right—and you need to find the value closest to a given target, like picking the nearest star in a sky full of numbers. That’s the delightful challenge of LeetCode 270: Closest BST Value! This easy-level problem asks you to find the integer in a BST that’s closest to a target floating-point number. Using Python, we’ll explore two solutions: the Best Solution, an iterative BST traversal that walks the tree efficiently, and an Alternative Solution, a recursive BST traversal that dives deep. With detailed examples, clear code, and friendly, easy-to-follow explanations—especially for the best solution—this guide will help you navigate BSTs and sharpen your coding skills. Let’s start hunting for that closest value!

What Is LeetCode 270: Closest BST Value?

In LeetCode 270: Closest BST Value, you’re given the root of a binary search tree (BST) and a target value (a float), and your task is to return the integer value in the tree that’s closest to the target. In a BST, each node’s left child is less than the node, and its right child is greater, making it perfect for narrowing down searches. This problem builds on BST basics from challenges like LeetCode 98: Validate Binary Search Tree, but focuses on finding the nearest match rather than validation.

Problem Statement

Input: A BST root node and a float target.
Output: An integer—the BST value closest to target.
Rules: BST properties hold (left < node < right); return the integer with the smallest absolute difference from target.

Constraints

Number of nodes: 1 to 10^4.
Node values: -10^9 to 10^9.
target: -10^9 to 10^9 (float).

Examples

Input:

Tree: Root: 4, Left: 2 (Left: 1, Right: 3), Right: 5
Target: 3.714286
Output: 4 (closest to 3.714286: |4 - 3.714286| ≈ 0.285714 vs. |3 - 3.714286| ≈ 0.714286).

Input:

Tree: Root: 1
Target: 4.428571
Output: 1 (only value).

Input:

Tree: Root: 3, Left: 2, Right: 4
Target: 2.5
Output: 2 (|2 - 2.5| = 0.5 < |3 - 2.5| = 0.5, but 2 is leftmost).

Understanding the Problem: Finding the Closest Match

To solve LeetCode 270: Closest BST Value in Python, we need to search a BST for the integer value with the smallest absolute difference from a target float. In a BST, we can use the ordering (left < node < right) to guide us toward the target, comparing each node’s value and tracking the closest one found. A basic way—visiting every node—works but wastes time. We’ll use two methods: 1. Best Solution (Iterative BST Traversal): O(h) time—fast and lean (h is tree height). 2. Alternative Solution (Recursive BST Traversal): O(h) time—clear but uses stack space.

Let’s dive into the best solution with a friendly, detailed walkthrough.

Best Solution: Iterative BST Traversal

Why This Is the Best Solution

The iterative BST traversal approach is the top pick for LeetCode 270 because it runs in O(h) time—where h is the tree height—and uses O(1) space, avoiding recursion overhead. It walks the tree like a treasure hunter, moving left or right based on the target, and keeps track of the closest value with minimal fuss, making it both quick and efficient.

How It Works

Picture this solution as a guided hike through the BST: you start at the root, compare the target to each node, and decide whether to head left (smaller) or right (bigger), updating your “closest” guess as you go. Since the BST is ordered, you can skip entire branches, homing in on the target. Here’s how it works, step-by-step, explained simply:

Step 1: Start at the Root:

Begin with the root node and set its value as your initial “closest” guess.

Step 2: Walk the Tree:

While you have a node:

Compare its value to the target.
Update closest if this node’s value is nearer (smaller absolute difference).
If target < node value, go left (smaller numbers).
If target > node value, go right (bigger numbers).

Step 3: Use BST Order:

The BST property ensures you’re always moving closer to the target or confirming the current node’s closeness.

Step 4: Finish When No More Nodes:

Stop when you hit a leaf (no left or right child in the direction you’re going).

Step 5: Return Closest:

The last updated closest is your answer.

It’s like following a map—each step gets you nearer to the treasure, and you keep the best find in your pocket!

Step-by-Step Example

Example: Tree: Root: 4, Left: 2 (Left: 1, Right: 3), Right: 5; Target: 3.714286

Text Representation:

Root: 4
Left: 2

Left: 1
Right: 3

Right: 5

Step 1: Start at root 4, closest = 4, diff = |4 - 3.714286| ≈ 0.285714.
Step 2: Target 3.714286 < 4, go left to 2.
Step 3: At 2, diff = |2 - 3.714286| ≈ 1.714286 > 0.285714, keep closest = 4.
Step 4: Target 3.714286 > 2, go right to 3.
Step 5: At 3, diff = |3 - 3.714286| ≈ 0.714286 > 0.285714, keep closest = 4.
Step 6: Target 3.714286 > 3, no right child, stop.
Result: 4.

Example: Tree: Root: 3, Left: 2, Right: 4; Target: 2.5

Text Representation:

Root: 3
Left: 2
Right: 4

Step 1: Start at 3, closest = 3, diff = |3 - 2.5| = 0.5.
Step 2: Target 2.5 < 3, go left to 2.
Step 3: At 2, diff = |2 - 2.5| = 0.5, keep closest = 2 (equal diff, take lower).
Step 4: Target 2.5 > 2, no right child, stop.
Result: 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained in a friendly way:

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:
        # Step 1: Start with root as closest
        closest = root.val

        # Step 2: Walk the tree
        curr = root
        while curr:
            # Update closest if current is nearer
            closest = min(closest, curr.val, key=lambda x: abs(target - x))

            # Step 3: Decide direction
            if target < curr.val:
                curr = curr.left  # Go left for smaller
            elif target > curr.val:
                curr = curr.right  # Go right for bigger
            else:
                break  # Exact match, stop

        # Step 4: Return the closest value
        return closest

Line 8-9: Set closest to root’s value to start.
Line 11-12: Use curr to traverse, starting at root.
Line 13-20: While curr exists:

Update closest using min with absolute difference as key.
If target < current, go left; if >, go right; if equal, stop (exact match).

Line 22: Return the final closest.

Time Complexity: O(h)—where h is tree height, logarithmic in balanced BSTs.
Space Complexity: O(1)—no extra space beyond variables.

This solution is like a smart compass—guides you straight to the closest spot!

Alternative Solution: Recursive BST Traversal

Why an Alternative Approach?

The recursive BST traversal method dives into the tree with function calls, checking each node and its subtrees to find the closest value. It’s also O(h) time but uses O(h) space for the call stack, offering a clear, tree-like way to explore the problem before switching to iteration.

How It Works

Think of this as sending scouts down the tree: at each node, check its value, then explore left or right based on the target, keeping the best guess as you climb back up. Here’s how it works, step-by-step:

Step 1: Start at root, track closest with a variable.
Step 2: Recursively:

Check current node’s closeness.
If target < node, recurse left.
If target > node, recurse right.
Update closest with min of current and subtree result.

Step 3: Return final closest.

It’s like climbing a tree—check each branch and report back the best find!

Step-by-Step Example

Example: Tree: Root: 4, Left: 2 (Left: 1, Right: 3), Right: 5; Target: 3.714286

Text Representation:

Root: 4
Left: 2

Left: 1
Right: 3

Right: 5

Step 1: At 4, diff = 0.285714, closest = 4.
Step 2: Target < 4, go left to 2.
Step 3: At 2, diff = 1.714286, closest = 4, Target > 2, go right to 3.
Step 4: At 3, diff = 0.714286, closest = 4, no right child.
Step 5: Backtrack, closest = 4.
Result: 4.

Code for Recursive Approach

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:
        def dfs(node):
            if not node:
                return float('inf')  # Base case: far away

            # Current difference
            curr_diff = abs(node.val - target)
            closest = node.val

            # Decide direction
            if target < node.val and node.left:
                left_closest = dfs(node.left)
                if abs(left_closest - target) < curr_diff:
                    closest = left_closest
            elif target > node.val and node.right:
                right_closest = dfs(node.right)
                if abs(right_closest - target) < curr_diff:
                    closest = right_closest

            return closest

        return dfs(root)

Time Complexity: O(h)—traverses height.
Space Complexity: O(h)—recursion stack.

It’s a deep dive with a clear view.

Comparing the Two Solutions

Best Solution (Iterative):

Pros: O(h) time, O(1) space, fast and lean.
Cons: Iterative logic to follow.

Alternative Solution (Recursive):

Pros: O(h) time, tree-like flow.
Cons: O(h) space, recursion overhead.

Iterative wins for efficiency.

Additional Examples and Edge Cases

Single Node

Root: 1, Target: 2 → 1

Left-Heavy

Root: 3, Left: 2, Left: 1, Target: 1.5 → 2

Right-Heavy

Root: 1, Right: 2, Right: 3, Target: 2.5 → 2

Both handle these well.

Complexity Breakdown

Iterative:

Time: O(h)—height traversal.
Space: O(1)—minimal.

Recursive:

Time: O(h)—height traversal.
Space: O(h)—stack.

Iterative is leaner.

Key Takeaways

Iterative: Walk smartly with BST order.
Recursive: Dive deep, climb back.
BST: Order guides the search.
Python Tip: Loops save space—see [Python Basics](/python/basics).

Final Thoughts: Find Closest Values Like a Pro

LeetCode 270: Closest BST Value in Python is a charming BST treasure hunt. The iterative solution zips through efficiently, while recursive offers a scenic route. Want more? Try LeetCode 98: Validate BST or LeetCode 285: Inorder Successor in BST. Ready to search? Head to Solve LeetCode 270 on LeetCode and snag that closest value today!