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
- An in-order traversal of a BST yields the values in ascending order.
- Once sorted, the
kclosest values form a contiguous window around the insertion point oftarget. - Use two pointers starting at the insertion point and expand outward, always taking the closer side.
- 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.