NUHMAN.com

Introduction

LeetCode 272: Closest Binary Search Tree Value II extends the concept from LeetCode 270 by asking for the k closest values to a given target, instead of just one.

This problem combines binary search tree traversal with two-pointer or stack-based windowing, and is a solid test of tree algorithms in interviews.

Problem Statement

Given the root of a BST, a target value, and an integer k, return the k values in the BST that are closest to the target.

Examples

python

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

Input: root = [1], target = 0.000000, k = 1
Output: [1]

✅ Step-by-Step Solution in Python

There are two main approaches:

✅ Approach 1: In-order Traversal + Heap (Max-Heap of Size k)

🔍 Key Idea

• Perform an in-order traversal to get sorted values
• Use a max-heap of size k to keep track of the closest values to the target

🧠 Why In-order?

In BST, in-order traversal gives a sorted list. This makes it easier to process nodes based on proximity to the target.

✅ Code (Heap-Based)

python

import heapq

def closestKValues(root, target, k):
    heap = []

    def inorder(node):
        if not node:
            return
        inorder(node.left)
        diff = abs(node.val - target)
        heapq.heappush(heap, (-diff, node.val))  # max-heap via negation
        if len(heap) > k:
            heapq.heappop(heap)
        inorder(node.right)

    inorder(root)
    return [val for _, val in heap]

🧠 Time & Space Complexity

• Time: O(n log k)
• Space: O(k)

✅ Approach 2: Two Stacks – Predecessors & Successors

🔍 Key Idea

• Use two stacks:
• predecessors = values less than or equal to target
• successors = values greater than target
• Pick the closest from either stack k times

✅ Code (Optimal Stack-Based)

python

def closestKValues(root, target, k):
    def push_predecessors(node):
        while node:
            if node.val <= target:
                predecessors.append(node)
                node = node.right
            else:
                node = node.left

    def push_successors(node):
        while node:
            if node.val > target:
                successors.append(node)
                node = node.left
            else:
                node = node.right

    def get_next(stack, is_predecessor):
        node = stack.pop()
        val = node.val
        nxt = node.left if is_predecessor else node.right
        while nxt:
            stack.append(nxt)
            nxt = nxt.right if is_predecessor else nxt.left
        return val

    predecessors, successors = [], []
    push_predecessors(root)
    push_successors(root)

    res = []
    for _ in range(k):
        if not predecessors:
            res.append(get_next(successors, False))
        elif not successors:
            res.append(get_next(predecessors, True))
        else:
            if abs(predecessors[-1].val - target) < abs(successors[-1].val - target):
                res.append(get_next(predecessors, True))
            else:
                res.append(get_next(successors, False))
    return res

🧠 Time & Space Complexity

• Time: O(k log n)
• Space: O(h + k), where h is the height of the tree

🧪 Dry Run

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

• Closest values: 4 and 3

✅ Output: [4, 3]

🧩 Edge Cases

• Only one node → return that node
• Target is outside BST range → should still return k nearest
• Tree is skewed → works fine

✅ Conclusion

LeetCode 272: Closest Binary Search Tree Value II pushes you to:

• Combine tree traversal with heap or stack-based decision making
• Use BST properties efficiently for k-value proximity