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

Imagine you’re wandering through a binary search tree (BST), where numbers are neatly sorted—smaller ones on the left, bigger ones on the right—and you need to find not just one, but the k closest values to a target number, like picking the k nearest stars in a twinkling sky. That’s the exciting challenge of LeetCode 272: Closest BST Value II! This hard-level problem asks you to return the k values in a BST that are closest to a given target float. Using Python, we’ll explore two solutions: the Best Solution, an inorder traversal with a sliding window that’s fast and efficient, and an Alternative Solution, a min-heap approach that’s straightforward but heavier. With detailed examples, clear code, and friendly, easy-to-follow explanations—especially for the best solution—this guide will help you master BST searches and boost your coding skills. Let’s start finding those k closest values!

What Is LeetCode 272: Closest BST Value II?

In LeetCode 272: Closest BST Value II, you’re given the root of a binary search tree (BST), a target value (a float), and an integer k. Your task is to return a list of the k integer values in the tree closest to the target, in any order. In a BST, left children are less than their parent, and right children are greater, making it ideal for ordered searches. This problem builds on LeetCode 270: Closest BST Value, expanding from one closest value to k closest values.

Problem Statement

Input: A BST root node, a float target, and an integer k.
Output: A list of k integers—the k values in the BST closest to target.
Rules: BST properties hold (left < node < right); return k values with smallest absolute differences; order doesn’t matter.

Constraints

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

Examples

Input:

Tree: Root: 4, Left: 2 (Left: 1, Right: 3), Right: 5
Target: 3.714286
k: 2
Output: [4, 3] (closest: 4 (|0.285714|), 3 (|0.714286|)).

Input:

Tree: Root: 1
Target: 0.0
k: 1
Output: [1] (only value).

Input:

Tree: Root: 3, Left: 2, Right: 4
Target: 2.5
k: 2
Output: [2, 3] (|2 - 2.5| = 0.5, |3 - 2.5| = 0.5).

Understanding the Problem: Picking k Closest Values

To solve LeetCode 272: Closest BST Value II in Python, we need to find the k BST values with the smallest absolute differences from a target float. The BST’s ordering (left < node < right) helps us search efficiently, but we need k values, not just one. A basic way—collecting all values and sorting by difference—works but wastes time (O(n log n)). We’ll use two methods: 1. Best Solution (Inorder Traversal with Sliding Window): O(n) time—fast and smart. 2. Alternative Solution (Min-Heap): O(n log k) time—clear but heavier.

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

Best Solution: Inorder Traversal with Sliding Window

Why This Is the Best Solution

The inorder traversal with sliding window approach is the top pick for LeetCode 272 because it runs in O(n) time—where n is the number of nodes—and uses O(k) space, leveraging the BST’s sorted nature to keep only the k closest values without extra sorting. It’s like walking through the tree in order, keeping a short list of the k best matches, and sliding out the farthest as you go, making it both quick and memory-efficient.

How It Works

Picture this solution as strolling through the BST in order (smallest to largest), carrying a little basket that holds k numbers. As you pick up each new value, you check if it’s closer to the target than the farthest in your basket—if so, swap it in and slide the old one out. Here’s how it works, step-by-step, explained simply:

Step 1: Use Inorder Traversal:

In a BST, inorder traversal (left, root, right) visits nodes in ascending order.
Use a stack to walk the tree iteratively, collecting values from smallest to largest.

Step 2: Keep a Window of k Values:

Use a deque (double-ended queue) to hold k values, adding new ones and removing the farthest when full.
Track differences from the target to decide what stays.

Step 3: Slide the Window:

For each new value:

If deque < k, add it.
If deque = k, compare new value’s diff with the farthest (leftmost if ascending); if closer, pop left, append right.

Step 4: Stop Early (Optimization):

Since values increase, if a new value’s diff exceeds the farthest in the deque, all remaining values will be farther—stop.

Step 5: Return the k Closest:

The deque holds the k closest values.

It’s like picking k best friends—keep the closest, swap out the farthest as you meet new ones!

Step-by-Step Example

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

Text Representation:

Root: 4
Left: 2

Left: 1
Right: 3

Right: 5

Step 1: Inorder: 1, 2, 3, 4, 5.
Step 2: Deque starts empty, k = 2.
Step 3: Process values:

1: Diff = |1 - 3.714286| ≈ 2.714286, Deque = [1].
2: Diff ≈ 1.714286, Deque = [1, 2].
3: Diff ≈ 0.714286, Farthest (1) = 2.714286 > 0.714286, Deque = [2, 3].
4: Diff ≈ 0.285714 < 1.714286 (farthest 2), Deque = [3, 4].
5: Diff ≈ 1.285714 > 0.714286 (farthest 3), stop (ascending, all worse).

Step 4: Deque = [3, 4].
Result: [3, 4].

Code with Detailed Line-by-Line Explanation

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

from collections import deque

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

class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        # Step 1: Set up deque for k closest
        window = deque()

        # Step 2: Inorder traversal with stack
        stack = []
        curr = root
        while curr or stack:
            # Go left as far as possible
            while curr:
                stack.append(curr)
                curr = curr.left

            # Process current node
            curr = stack.pop()
            val = curr.val
            diff = abs(val - target)

            # Step 3: Manage sliding window
            if len(window) < k:
                window.append(val)  # Add if less than k
            else:
                # Compare with farthest (leftmost)
                farthest_diff = abs(window[0] - target)
                if diff < farthest_diff:
                    window.popleft()  # Remove farthest
                    window.append(val)  # Add closer
                elif val > target:
                    break  # Ascending, all further are worse

            # Move to right subtree
            curr = curr.right

        # Step 4: Return k closest values
        return list(window)

Line 10-11: Create a deque to hold k values.
Line 13-16: Use a stack for inorder traversal, start at root.
Line 17-22: Push all left nodes onto stack.
Line 24-35: Pop node, process value:

If deque < k, append.
If full, compare diff with farthest; if closer, slide window; if farther and past target, stop.

Line 37: Move to right subtree.
Line 39: Return deque as list.

Time Complexity: O(n)—traverses all nodes in worst case.
Space Complexity: O(k + h)—deque (k) and stack (h, height).

This solution is like a smart picker—grabs k best matches on the go!

Alternative Solution: Min-Heap Approach

Why an Alternative Approach?

The min-heap approach collects all BST values and their differences from the target, then picks the k smallest using a heap. It’s O(n log k) time—slower but intuitive—using O(n) space, offering a clear way to see all options before optimizing with traversal.

How It Works

Think of this as gathering all stars in a heap, ranking them by distance from your target, and plucking the k nearest. Here’s how it works, step-by-step:

Step 1: Traverse BST, store (diff, value) pairs in a heap.
Step 2: Keep heap size at k by popping largest diffs.
Step 3: Extract k values from heap.

It’s like sorting a pile—keep the k best shining through!

Step-by-Step Example

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

Step 1: Values: [1, 2, 3, 4, 5].
Step 2: Heap (max-heap of diffs, k size):

(2.714286, 1), (1.714286, 2) → [(2.714286, 1), (1.714286, 2)].
(0.714286, 3): Pop (2.714286, 1), add → [(1.714286, 2), (0.714286, 3)].
(0.285714, 4): Pop (1.714286, 2), add → [(0.714286, 3), (0.285714, 4)].
(1.285714, 5): Keep → [(0.714286, 3), (0.285714, 4)].

Step 3: Extract: [3, 4].
Result: [3, 4].

Code for Min-Heap Approach

import heapq

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

class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        # Step 1: Collect all values with diffs in heap
        heap = []

        def inorder(node):
            if not node:
                return
            inorder(node.left)
            # Max-heap: use negative diff to pop largest
            heapq.heappush(heap, (-abs(node.val - target), node.val))
            if len(heap) > k:
                heapq.heappop(heap)
            inorder(node.right)

        inorder(root)

        # Step 2: Extract k values
        return [val for _, val in heap]

Time Complexity: O(n log k)—n insertions, k heap size.
Space Complexity: O(k)—heap size.

It’s a heap-powered picker—steady but bulkier.

Comparing the Two Solutions

Best Solution (Inorder Window):

Pros: O(n) time, O(k + h) space, efficient.
Cons: Window logic to grasp.

Alternative Solution (Min-Heap):

Pros: O(n log k) time, O(k) space, intuitive heap.
Cons: Slower, more memory.

Inorder wins for speed.

Additional Examples and Edge Cases

Single Node

Root: 1, Target: 2, k: 1 → [1]

All Equal Diffs

Root: 2, Left: 1, Right: 3, Target: 2, k: 2 → [1, 2]

Large k

Root: 3, Left: 1, Right: 5, Target: 4, k: 3 → [1, 3, 5]

Both handle these well.

Complexity Breakdown

Inorder Window:

Time: O(n)—full traversal.
Space: O(k + h)—deque and stack.

Min-Heap:

Time: O(n log k)—heap ops.
Space: O(k)—heap.

Inorder is faster.

Key Takeaways

Inorder Window: Slide through smartly.
Min-Heap: Heap sorts diffs.
BST: Order aids efficiency.
Python Tip: Deques flex for windows—see [Python Basics](/python/basics).

Final Thoughts: Find k Closest Like a Pro

LeetCode 272: Closest BST Value II in Python is a stellar BST challenge. The inorder solution glides through efficiently, while the min-heap piles up options. Want more? Try LeetCode 270: Closest BST Value or LeetCode 230: Kth Smallest Element in BST. Ready to hunt? Head to Solve LeetCode 272 on LeetCode and grab those k closest values today!