2476. Closest Nodes Queries in a Binary Search Tree LeetCode Solution
In this guide, you will get 2476. Closest Nodes Queries in a Binary Search Tree LeetCode Solution with the best time and space complexity. The solution to Closest Nodes Queries in a Binary Search Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Closest Nodes Queries in a Binary Search Tree
You are given the root of a binary search tree and an array queries of size n consisting of positive integers.
Find a 2D array answer of size n where answer[i] = [mini, maxi]:
mini is the largest value in the tree that is smaller than or equal to queries[i]. If a such value does not exist, add -1 instead.
maxi is the smallest value in the tree that is greater than or equal to queries[i]. If a such value does not exist, add -1 instead.
Return the array answer.
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: We answer the queries in the following way:
– The largest number that is smaller or equal than 2 in the tree is 2, and the smallest number that is greater or equal than 2 is still 2. So the answer for the first query is [2,2].
– The largest number that is smaller or equal than 5 in the tree is 4, and the smallest number that is greater or equal than 5 is 6. So the answer for the second query is [4,6].
– The largest number that is smaller or equal than 16 in the tree is 15, and the smallest number that is greater or equal than 16 does not exist. So the answer for the third query is [15,-1].
Input: root = [4,null,9], queries = [3]
Output: [[-1,4]]
Explanation: The largest number that is smaller or equal to 3 in the tree does not exist, and the smallest number that is greater or equal to 3 is 4. So the answer for the query is [-1,4].
Constraints:
The number of nodes in the tree is in the range [2, 105].
1 <= Node.val <= 106
n == queries.length
1 <= n <= 105
1 <= queries[i] <= 106
Complexity Analysis
Time Complexity: O(n + q\log n)
Space Complexity: O(n + q)
2476. Closest Nodes Queries in a Binary Search Tree LeetCode Solution in C++
class Solution {
public:
vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
vector<vector<int>> ans;
vector<int> sortedVals;
inorder(root, sortedVals);
for (const int query : queries) {
const auto it = ranges::lower_bound(sortedVals, query);
// query is presented in the tree, so just use {query, query}.
if (it != sortedVals.cend() && *it == query)
ans.push_back({query, query});
// query isn't presented in the tree, so find the cloest one if possible.
else
ans.push_back({it == sortedVals.cbegin() ? -1 : *prev(it),
it == sortedVals.cend() ? -1 : *it});
}
return ans;
}
private:
// Walks the BST to collect the sorted numbers.
void inorder(TreeNode* root, vector<int>& sortedVals) {
if (root == nullptr)
return;
inorder(root->left, sortedVals);
sortedVals.push_back(root->val);
inorder(root->right, sortedVals);
}
}; /* code provided by PROGIEZ */
2476. Closest Nodes Queries in a Binary Search Tree LeetCode Solution in Java
class Solution {
public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> sortedVals = new ArrayList<>();
inorder(root, sortedVals);
for (final int query : queries) {
final int i = firstGreaterEqual(sortedVals, query);
// query is presented in the tree, so just use {query, query}.
if (i != sortedVals.size() && sortedVals.get(i) == query)
ans.add(Arrays.asList(query, query));
// query isn't presented in the tree, so find the cloest one if possible.
else
ans.add(Arrays.asList(i == 0 ? -1 : sortedVals.get(i - 1),
i == sortedVals.size() ? -1 : sortedVals.get(i)));
}
return ans;
}
// Walks the BST to collect the sorted numbers.
private void inorder(TreeNode root, List<Integer> sortedVals) {
if (root == null)
return;
inorder(root.left, sortedVals);
sortedVals.add(root.val);
inorder(root.right, sortedVals);
}
private int firstGreaterEqual(List<Integer> A, int target) {
final int i = Collections.binarySearch(A, target);
return i < 0 ? -i - 1 : i;
}
} // code provided by PROGIEZ
2476. Closest Nodes Queries in a Binary Search Tree LeetCode Solution in Python
class Solution:
def closestNodes(self, root: TreeNode | None, queries: list[int]) -> list[list[int]]:
sortedVals = []
self._inorder(root, sortedVals)
def getClosestPair(query: int) -> list[int]:
i = bisect_left(sortedVals, query)
# query is presented in the tree, so just use [query, query].
if i != len(sortedVals) and sortedVals[i] == query:
return [query, query]
# query isn't presented in the tree, so find the cloest one if possible.
return [-1 if i == 0 else sortedVals[i - 1],
-1 if i == len(sortedVals) else sortedVals[i]]
return [getClosestPair(query) for query in queries]
def _inorder(self, root: TreeNode | None, sortedVals: list[int]) -> None:
"""Walks the BST to collect the sorted numbers."""
if not root:
return
self._inorder(root.left, sortedVals)
sortedVals.append(root.val)
self._inorder(root.right, sortedVals) # code by PROGIEZ
