272. Closest Binary Search Tree Value II
Asked at LinkedIn
Difficulty
Hard
Time
O(n)
Space
O(h + k)
Pattern
Two Pointers
Companies
1
Problem
You are given the root of a binary search tree (BST), a target number target (it may have a fractional part), and an integer k. Return the k values in the tree that are closest to target.
"Closest" means smallest absolute difference: abs(value - target). The answer may be in any order. The problem guarantees that there is exactly one set of k values that is closest, so you never have to break a tie.
A BST has a useful property: if you read its values from left to right (an inorder traversal), they come out in sorted order. So the k closest values always sit next to each other in that sorted list — they form a window of size k.
Pick the k nearest values
Constraints
- ●
1 <= k <= n <= 10^4, where n is the number of nodes - ●
0 <= Node.val <= 10^9 - ●
-10^9 <= target <= 10^9
Examples
root = [4,2,5,1,3], target = 3.714286, k = 2[4,3]root = [1], target = 0.000000, k = 1[1]Asked At
1 companies| 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).
Sliding window during inorder
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
O(n) timefrom 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 runs in O(n) time and O(h + k) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.