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].
Example 2:
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:
[2, 105].1 <= Node.val <= 106n == queries.length1 <= n <= 1051 <= queries[i] <= 106This approach involves performing an in-order traversal of the BST to acquire a sorted list of all node values. An in-order traversal naturally provides the values in ascending order for a BST.
Once we have the sorted list of values, we can use binary search to effectively find the closest values for each query. We look for the largest value smaller or equal (MIN) and the smallest value larger or equal (MAX) using binary search.
The C solution involves creating an additional space to store the sorted node values from an in-order traversal. We then apply binary search to find the closest values for each query in O(log n) time, making the overall solution efficient.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m log n), where n is the number of nodes in the tree and m is the number of queries.
Space Complexity: O(n) due to the storage of sorted node values.
This approach deals directly with recursive traversals of the tree for each query. For each query, position ourselves at the root, and move left if the query value is less than the current node, right otherwise, updating potential candidate values as needed to determine closest lower and upper values.
The C implementation handles each query via recursive calls traversing the tree. It keeps track of potential min and max values as it traverses left or right to efficiently resolve each query.
C++
Java
Python
C#
JavaScript
Time Complexity: O(h) per query, where h is the height of the tree, resulting in O(m * h) in total.
Space Complexity: O(h) for recursion stack.
| Approach | Complexity |
|---|---|
| In-order Traversal and Binary Search | Time Complexity: O(n + m log n), where n is the number of nodes in the tree and m is the number of queries. Space Complexity: O(n) due to the storage of sorted node values. |
| Recursive Query Processing without Additional Inorder List | Time Complexity: O(h) per query, where h is the height of the tree, resulting in O(m * h) in total. Space Complexity: O(h) for recursion stack. |
Validate Binary Search Tree - Depth First Search - Leetcode 98 • NeetCode • 257,702 views views
Watch 9 more video solutions →Practice Closest Nodes Queries in a Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCode