Closest Binary Search Tree Value II
Closest Binary Search Tree Value II is a hard trees & bst problem solved with the bst basics pattern.
The best approach, optimal (predecessor and successor stacks), runs in O(h + k) time and O(h) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (collect and sort by distance) up.
Problem
You are given the root of a binary search tree, a real number target and an integer k. Return the k values in the tree that are closest to target, measured by absolute difference.
You may return the values in any order. The input is chosen so that exactly one set of k values is closest (no ties at the cut-off).
Can you do better than O(n) when the tree is balanced and k is much smaller than n?
Examples
Example 1
- Input
root = [8,4,12,2,6,10,14], target = 7.3, k = 3- Output
[8,6,10]- Why
- The distances to 7.3 are 0.7 for 8, 1.3 for 6 and 2.7 for 10; every other value is farther away.
Example 2
- Input
root = [5], target = 1.9, k = 1- Output
[5]- Why
- The only value in the tree is the answer, however far it is.
Example 3
- Input
root = [20,10,30,null,15], target = 26.0, k = 2- Output
[30,20]- Why
- 30 is 4 away and 20 is 6 away, while 15 is 11 away and 10 is 16 away.
Constraints
- The tree has
nnodes,1 <= k <= n <= 10^4. 0 <= Node.val <= 10^9, and all values are distinct (the tree is a valid BST).-10^9 <= target <= 10^9- The set of
kclosest values is unique. The values may be returned in any order.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (collect and sort by distance) | O(n log n) | O(n) |
| Optimal (predecessor and successor stacks) | O(h + k) | O(h) |
1Brute force (collect and sort by distance)
O(n log n)Every value is visited once and then the n values are sorted.O(n)The list of all values plus the recursion stack.Gather every value with any traversal, sort them by their distance to the target, and keep the first k.
- Traverse the tree and put all values in a list.
- Sort the list by |value - target|.
- Return the first k values.
class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> all = new ArrayList<>();
collect(root, all);
all.sort((a, b) -> Double.compare(Math.abs(a - target), Math.abs(b - target)));
return new ArrayList<>(all.subList(0, k));
}
private void collect(TreeNode node, List<Integer> all) {
if (node == null) return;
collect(node.left, all);
all.add(node.val);
collect(node.right, all);
}
}class Solution:
def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:
values = []
def collect(node):
if node is None:
return
collect(node.left)
values.append(node.val)
collect(node.right)
collect(root)
values.sort(key=lambda v: abs(v - target))
return values[:k]class Solution {
public:
vector<int> closestKValues(TreeNode* root, double target, int k) {
vector<int> all;
collect(root, all);
sort(all.begin(), all.end(), [&](int a, int b) {
return fabs(a - target) < fabs(b - target);
});
return vector<int>(all.begin(), all.begin() + k);
}
private:
void collect(TreeNode* node, vector<int>& all) {
if (node == nullptr) return;
collect(node->left, all);
all.push_back(node->val);
collect(node->right, all);
}
};function closestKValues(root, target, k) {
const all = [];
const collect = (node) => {
if (node === null) return;
collect(node.left);
all.push(node.val);
collect(node.right);
};
collect(root);
all.sort((a, b) => Math.abs(a - target) - Math.abs(b - target));
return all.slice(0, k);
}2Optimal (predecessor and successor stacks)
O(h + k)Priming walks one path of height h, and the k pops push each node at most once, adding O(h + k) total.O(h)Each stack holds at most one root-to-leaf path.Think of the in-order sequence as a sorted array split at the target. The answer is the k values nearest that split. One stack produces the values <= target from largest to smallest (in-order predecessors), another produces the values > target from smallest to largest (in-order successors). Like merging two sorted lists, take whichever next value is closer, k times. Each stack is primed by one root-to-leaf walk, and every node is pushed at most once afterwards.
- Prime pred: walk from the root; when node.val <= target push it and go right, otherwise go left.
- Prime succ: walk from the root; when node.val > target push it and go left, otherwise go right.
- Repeat k times: if one stack is empty take from the other; else take from pred if target - pred.top <= succ.top - target, otherwise from succ.
- Taking from pred: pop node, record its value, then push node.left and its chain of right children. Taking from succ: pop node, record it, then push node.right and its chain of left children.
class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
Deque<TreeNode> pred = new ArrayDeque<>(), succ = new ArrayDeque<>();
for (TreeNode n = root; n != null; ) {
if (n.val <= target) { pred.push(n); n = n.right; }
else n = n.left;
}
for (TreeNode n = root; n != null; ) {
if (n.val > target) { succ.push(n); n = n.left; }
else n = n.right;
}
List<Integer> res = new ArrayList<>();
while (res.size() < k) {
boolean takePred;
if (succ.isEmpty()) takePred = true;
else if (pred.isEmpty()) takePred = false;
else takePred = target - pred.peek().val <= succ.peek().val - target;
if (takePred) {
TreeNode n = pred.pop();
res.add(n.val);
for (TreeNode c = n.left; c != null; c = c.right) pred.push(c);
} else {
TreeNode n = succ.pop();
res.add(n.val);
for (TreeNode c = n.right; c != null; c = c.left) succ.push(c);
}
}
return res;
}
}class Solution:
def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:
pred, succ = [], []
n = root
while n:
if n.val <= target:
pred.append(n)
n = n.right
else:
n = n.left
n = root
while n:
if n.val > target:
succ.append(n)
n = n.left
else:
n = n.right
res = []
while len(res) < k:
if not succ:
take_pred = True
elif not pred:
take_pred = False
else:
take_pred = target - pred[-1].val <= succ[-1].val - target
if take_pred:
n = pred.pop()
res.append(n.val)
c = n.left
while c:
pred.append(c)
c = c.right
else:
n = succ.pop()
res.append(n.val)
c = n.right
while c:
succ.append(c)
c = c.left
return resclass Solution {
public:
vector<int> closestKValues(TreeNode* root, double target, int k) {
vector<TreeNode*> pred, succ;
for (TreeNode* n = root; n != nullptr; ) {
if (n->val <= target) { pred.push_back(n); n = n->right; }
else n = n->left;
}
for (TreeNode* n = root; n != nullptr; ) {
if (n->val > target) { succ.push_back(n); n = n->left; }
else n = n->right;
}
vector<int> res;
while ((int) res.size() < k) {
bool takePred;
if (succ.empty()) takePred = true;
else if (pred.empty()) takePred = false;
else takePred = target - pred.back()->val <= succ.back()->val - target;
if (takePred) {
TreeNode* n = pred.back(); pred.pop_back();
res.push_back(n->val);
for (TreeNode* c = n->left; c != nullptr; c = c->right) pred.push_back(c);
} else {
TreeNode* n = succ.back(); succ.pop_back();
res.push_back(n->val);
for (TreeNode* c = n->right; c != nullptr; c = c->left) succ.push_back(c);
}
}
return res;
}
};function closestKValues(root, target, k) {
const pred = [], succ = [];
for (let n = root; n !== null; ) {
if (n.val <= target) { pred.push(n); n = n.right; }
else n = n.left;
}
for (let n = root; n !== null; ) {
if (n.val > target) { succ.push(n); n = n.left; }
else n = n.right;
}
const res = [];
while (res.length < k) {
let takePred;
if (succ.length === 0) takePred = true;
else if (pred.length === 0) takePred = false;
else takePred = target - pred[pred.length - 1].val <= succ[succ.length - 1].val - target;
if (takePred) {
const n = pred.pop();
res.push(n.val);
for (let c = n.left; c !== null; c = c.right) pred.push(c);
} else {
const n = succ.pop();
res.push(n.val);
for (let c = n.right; c !== null; c = c.left) succ.push(c);
}
}
return res;
}Edge cases to test
k = n: every value is returned- Target smaller than every value, or larger than every value (all answers come from one side)
- Target equal to a value in the tree
- A skewed tree that is really a linked list
- A single node
Hints
Hint 1
An in-order traversal of a BST lists the values in sorted order. How would you find the k closest values in a sorted array?
Hint 2
In a sorted list, the answer is a contiguous block around the target: grow it from the split point one value at a time, always taking the nearer side.
Hint 3
You don't need the whole sorted list. Two stacks can walk the in-order sequence outward from the target, one to smaller values (predecessors) and one to larger values (successors), each step in amortised O(1).
FAQ
What is the best time complexity for Closest Binary Search Tree Value II?
Optimal (predecessor and successor stacks) runs in O(h + k) time and O(h) extra space. Priming walks one path of height h, and the k pops push each node at most once, adding O(h + k) total.
Which pattern does Closest Binary Search Tree Value II use?
It is a trees & bst problem that uses the bst basics pattern. Other problems with the same pattern: Search in a Binary Search Tree, Minimum element in BST, Insert into a Binary Search Tree.
Is there a brute force solution for Closest Binary Search Tree Value II?
Yes. Brute force (collect and sort by distance) takes O(n log n) time and O(n) space. Gather every value with any traversal, sort them by their distance to the target, and keep the first k.
Which edge cases should I test for Closest Binary Search Tree Value II?
k = n: every value is returned; Target smaller than every value, or larger than every value (all answers come from one side); Target equal to a value in the tree; A skewed tree that is really a linked list; A single node.