Closest Nodes Queries in a Binary Search Tree — Solution
Closest Nodes Queries in a Binary Search Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Closest Nodes Queries in a Binary Search Tree is a medium coding problem on arrays, depth-first search and binary search, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Arrays, Depth-First Search, Binary Search, Trees
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary search tree and an array queries of positive integers.
For each query q return a pair [mini, maxi] where:
miniis the largest value in the tree that is less than or equal toq, or-1if there is none;maxiis the smallest value in the tree that is greater than or equal toq, or-1if there is none.
Return the pairs in the order of the queries.
Example 1
Input: root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]
Output: [[2,2],[4,6],[15,-1]]
Explanation: 2 is in the tree, so both answers are 2. For 5 the closest values around it are 4 and 6. Nothing is at least 16, so its upper answer is -1.
Example 2
Input: root = [4,null,9], queries = [3]
Output: [[-1,4]]
Explanation: Nothing in the tree is at most 3; the smallest value at least 3 is 4.
Example 3
Input: root = [8,3], queries = [8,1,20]
Output: [[8,8],[-1,3],[8,-1]]
Explanation: 8 is in the tree, so it answers both sides. Nothing is at most 1 (the smallest value at least 1 is 3), and nothing is at least 20.
Constraints
2 <= number of nodes <= 10^51 <= Node.val <= 10^6root is a valid binary search tree with distinct values1 <= queries.length <= 10^51 <= queries[i] <= 10^6
Hints for Closest Nodes Queries in a Binary Search Tree
Hint 1
The tree can be badly unbalanced — a chain of 10^5 nodes — so walking it from the root once per query can be too slow.
Hint 2
An in-order traversal of a BST lists its values in increasing order. Do that once.
Hint 3
With the sorted list, each query is a binary search: the first value
>= qgivesmaxi, and the value just before it (or the found value itself when it equalsq) givesmini.
How to solve Closest Nodes Queries in a Binary Search Tree
Flatten the BST into its sorted in-order sequence once, then answer every query with one binary search for the first value not below it.
Approach
- Traverse the tree in order to collect its values in increasing order into
vals. - For a query
q, findi, the first index withvals[i] >= q(lower bound). maxiisvals[i]ifi < len(vals), else-1.miniisqwhenvals[i] == q; otherwisevals[i - 1]ifi > 0, else-1.
Why it works
vals is sorted, so every value before position i is below q and every value from i on is at least q. The smallest value at least q is therefore vals[i], and the largest value at most q is vals[i] itself when it equals q, or else the last value before it.
Complexity
- Time —
O(n + m log n) for n nodes and m queries - Space —
O(n) for the sorted values
Pitfalls
- Searching from the root per query costs O(height), which is O(n) on a skewed tree — 10^10 steps in the worst case.
- A query equal to a tree value answers
[q, q]; do not take the strictly smaller neighbour.
Reference solution
Python
from bisect import bisect_left
from typing import List, Optional
def closestNodes(root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
vals = []
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
vals.append(node.val)
node = node.right
out = []
for q in queries:
i = bisect_left(vals, q)
hi = vals[i] if i < len(vals) else -1
if i < len(vals) and vals[i] == q:
lo = q
else:
lo = vals[i - 1] if i > 0 else -1
out.append([lo, hi])
return outJava
public static int[][] closestNodes(TreeNode root, int[] queries) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) { stack.push(node); node = node.left; }
node = stack.pop();
list.add(node.val);
node = node.right;
}
int n = list.size();
int[] vals = new int[n];
for (int i = 0; i < n; i++) vals[i] = list.get(i);
int[][] out = new int[queries.length][];
for (int k = 0; k < queries.length; k++) {
int q = queries[k], lo = 0, hi = n;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (vals[mid] < q) lo = mid + 1; else hi = mid;
}
int maxi = lo < n ? vals[lo] : -1;
int mini = lo < n && vals[lo] == q ? q : (lo > 0 ? vals[lo - 1] : -1);
out[k] = new int[] { mini, maxi };
}
return out;
}C++
vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
vector<int> vals;
vector<TreeNode*> stack;
TreeNode* node = root;
while (!stack.empty() || node) {
while (node) { stack.push_back(node); node = node->left; }
node = stack.back();
stack.pop_back();
vals.push_back(node->val);
node = node->right;
}
vector<vector<int>> out;
for (int q : queries) {
int i = (int) (lower_bound(vals.begin(), vals.end(), q) - vals.begin());
int n = (int) vals.size();
int maxi = i < n ? vals[i] : -1;
int mini = i < n && vals[i] == q ? q : (i > 0 ? vals[i - 1] : -1);
out.push_back({mini, maxi});
}
return out;
}JavaScript
var closestNodes = function(root, queries) {
var vals = [], stack = [], node = root;
while (stack.length > 0 || node !== null) {
while (node !== null) { stack.push(node); node = node.left; }
node = stack.pop();
vals.push(node.val);
node = node.right;
}
var out = [];
for (var k = 0; k < queries.length; k++) {
var q = queries[k], lo = 0, hi = vals.length;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (vals[mid] < q) lo = mid + 1; else hi = mid;
}
var maxi = lo < vals.length ? vals[lo] : -1;
var mini = lo < vals.length && vals[lo] === q ? q : (lo > 0 ? vals[lo - 1] : -1);
out.push([mini, maxi]);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Depth-First Search (DFS)