⚡Flashcard Drill➔
NeetCode #413LC-272HardTreesNC Algo100
← Back to All Problems

#413 · #272 · Closest Binary Search Tree Value II(最接近的二叉搜索树值 II)

📌 Problem Statement & Constraints

Given the root of a binary search tree, a target and an integer k, return the k values in the BST closest to the target, in any order. Constraints: the number of nodes is in [1, 10^4], 1 <= k <= n, 0 <= Node.val, target <= 10^9.

💡 Core Algorithmic Approaches

  1. An in-order traversal of a BST yields the values in ascending order.
  2. Once sorted, the k closest values form a contiguous window around the insertion point of target.
  3. Use two pointers starting at the insertion point and expand outward, always taking the closer side.
  4. This is O(n) for the traversal plus O(k) for the expansion.

💻 Benchmark Python3 Implementation

class Solution:
    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:
        from bisect import bisect_left
        vals = []

        def inorder(node: Optional[TreeNode]) -> None:
            if not node:
                return
            inorder(node.left)
            vals.append(node.val)          # ascending order
            inorder(node.right)

        inorder(root)
        i = bisect_left(vals, target)      # insertion point
        lo, hi = i - 1, i                  # expand outward from here
        res = []
        while len(res) < k:
            if lo < 0:
                res.append(vals[hi]); hi += 1
            elif hi >= len(vals):
                res.append(vals[lo]); lo -= 1
            elif abs(vals[lo] - target) <= abs(vals[hi] - target):
                res.append(vals[lo]); lo -= 1
            else:
                res.append(vals[hi]); hi += 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + k): the in-order traversal plus the window expansion.
💾 Space Complexity
O(n) for the values array plus O(h) for the recursion.

⚠️ Interview Pitfalls & Follow-ups

  • Sorting by distance after collecting the values: O(n log n), whereas the sorted array makes the expansion linear.
  • Forgetting the two boundary cases: when one pointer runs off the end, the other side must supply all remaining values.
  • Using a heap of all values: O(n log k), workable but slower than the two-pointer expansion.
  • Assuming the values are distinct: the constraints allow duplicates, and the two-pointer logic handles them.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems