Closest Binary Search Tree Value II
Asked at LinkedIn
Problem
Closest Binary Search Tree Value II asks for the k values in a BST that are closest to a (possibly fractional) target. The BST property gives you the values in sorted order for free, which turns the problem into finding the best window of size k in a sorted sequence.
Asked At
| Company | Difficulty | |
|---|---|---|
| Hard | View all LinkedIn questions → |
How to Think About It
Simple approach: collect all values, sort by abs(v - target), take k. That is O(n log n) and ignores the BST ordering entirely.
Key insight: an inorder traversal visits values in sorted order, and the k closest values to any target form a contiguous window in that sorted order.
Maintain a deque of at most k values during the inorder walk. When it is full and the new value is closer than the leftmost one, drop the leftmost and append the new one. When the new value is not closer, stop — every later value is even farther away.
Walkthrough for [4,2,5,1,3], target 3.714286, k 2: inorder 1,2,3,4,5. Window fills with [1,2]; 3 is closer than 1 -> [2,3]; 4 is closer than 2 -> [3,4]; 5 is not closer than 3 -> stop. Answer [3,4].
Follow-up: the tree is balanced and you want better than O(n). Use two stacks (predecessors and successors) seeded by searching for the target, then merge like two pointers in O(k + log n).
Optimal Approach
Step 1: Do an inorder traversal (iteratively or recursively).
Step 2: For each visited value v:
If the deque has fewer than k values: append v.
Else if abs(v - target) < abs(dq[0] - target): pop left, append v.
Else: stop the traversal.
Step 3: Return the deque contents.
The early stop is valid because values only get larger (and farther from the target) after this point.
Time: O(n) worst case. Space: O(h + k).
What Trips People Up in Real Interviews
Sorting all values by distance. It works but throws away the BST ordering the interviewer gave you on purpose.
Using a max-heap of size k with no early exit. It is O(n log k) — fine, but mention the sorted-window argument that allows stopping early.
Comparing with the wrong end of the window. Values arrive in increasing order, so the value to evict is always the leftmost (smallest).
Integer-casting the target. The target is a double; keep distance comparisons in floating point.
Solution Code
from collections import deque
def closestKValues(root, target, k):
dq = deque()
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
v = node.val
if len(dq) < k:
dq.append(v)
elif abs(v - target) < abs(dq[0] - target):
dq.popleft()
dq.append(v)
else:
break
node = node.right
return list(dq)Frequently Asked Questions
What is the Closest Binary Search Tree Value II problem?
Closest Binary Search Tree Value II asks for the `k` values in a BST that are closest to a (possibly fractional) target. The BST property gives you the values in sorted order for free, which turns the problem into finding the best window of size `k` in a sorted sequence.
How do you solve Closest Binary Search Tree Value II?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Closest Binary Search Tree Value II?
Closest Binary Search Tree Value II is asked at LinkedIn. It is a hard difficulty problem.
What are common mistakes on Closest Binary Search Tree Value II?
- Sorting all values by distance. It works but throws away the BST ordering the interviewer gave you on purpose.
- Using a max-heap of size k with no early exit. It is `O(n log k)` — fine, but mention the sorted-window argument that allows stopping early.
- Comparing with the wrong end of the window. Values arrive in increasing order, so the value to evict is always the leftmost (smallest).
- Integer-casting the target. The target is a double; keep distance comparisons in floating point.