2476. Closest Nodes Queries in a Binary Search Tree
Problem Description
The given problem presents us with a binary search tree (BST) and a series of queries. Our task is to respond to each query with a pair of values based on the contents of the BST. Specifically, for each query, we need to find two values from the tree:
min_i
: The largest value in the tree that is less than or equal to the query value. If there's no such value, we should return-1
.max_i
: The smallest value in the tree that is greater than or equal to the query value. If there's no such value, we should return-1
.
The objective is to create a 2D array (a list of lists in Python) named answer
, where each element answer[i]
is a [min_i, max_i]
pair, corresponding to each query. The problem measures our understanding of BST navigation and the search for boundary conditions relative to arbitrary target values.
Flowchart Walkthrough
Let's examine the use of an algorithm using the Flowchart. Here's a step-by-step analysis to determine the appropriate algorithm for leetcode 2476. Closest Nodes Queries in a Binary Search Tree:
Is it a graph?
- Yes: A binary search tree is a specialized form of a graph, with nodes connected in a parent-child relationship.
Is it a tree?
- Yes: By definition, a Binary Search Tree (BST) is a tree.
DFS
- As determined by the flowchart, since we're dealing with a tree and no further specifications lead us beyond this decision in the chart, Depth-First Search (DFS) is the appropriate algorithm to use in this scenario.
Conclusion:
- The flowchart leads us directly to utilizing Depth-First Search (DFS) when we confirm that the problem is set within a tree structure, as is the case with binary search trees in leetcode 2476. DFS is ideally suited for problems involving tree structures because it can explore all nodes and edges from root to leaves deeply, which is key for various tree-related queries.
Intuition
In order to solve this challenge, we can leverage the properties of a binary search tree. A BST is organized in such a way that for any node with a value v
, any descendant node in its left subtree will have a value less than v
, and any descendant node in its right subtree will have a value greater than v
. This allows us to perform efficient tree traversals to find the min_i
and max_i
values for each query.
The provided solution takes the following steps:
-
Perform an in-order traversal of the BST and collect all the node values in a list called
nums
. In a BST, an in-order traversal guarantees that the values will be sorted in ascending order. This step is important because it then allows us to use binary search techniques to quickly locate the correctmin_i
andmax_i
values for each query. -
Iterate through each value in the
queries
list. For each query valuev
, we perform two binary search operations to find the closest values in the sorted listnums
that satisfy our conditions:-
To find
min_i
, we search for the insertion point ofv
as if we would insert it, then we take one step back (if we are not at the beginning of the list), as this would give us the largest value smaller than or equal tov
. -
To find
max_i
, we search for the insertion point directly, which gives us the smallest value greater than or equal tov
.
-
-
We check the index bounds to make sure we're adding legitimate values from our list or
-1
if the index is out of range (indicating that no such value exists in the BST for our query).
Using efficient binary search operations (bisect_left
and bisect_right
from the bisect
module in Python), the provided solution minimizes the search time to locate min_i
and max_i
, thereby optimizing the overall time complexity of the problem.
Learn more about Tree, Depth-First Search, Binary Search and Binary Tree patterns.
Solution Approach
The implementation of the solution follows a straightforward approach that breaks the problem into manageable steps as follows:
-
In-Order Traversal: Since we need to find the nearest values around each query from a binary search tree, we first collect these values in an organized manner. By performing an in-order traversal of the BST, we traverse left subtree, then the root, and finally the right subtree. The traversal yields a sorted array
nums
of all values in the BST in ascending order, where each element corresponds to the value of each node visited. -
Binary Search: With the sorted list of BST values, we then utilize binary search to quickly find the
min_i
andmax_i
for each query valuev
. Python’sbisect
module provides two handy functions to assist with this:-
bisect_right(nums, v)
returns the insertion point forv
in the listnums
. Ifv
is already innums
, the insertion point will be to the right of any existing entries. We subtract1
to find the largest value that is less than or equal tov
. -
bisect_left(nums, v)
returns the insertion point forv
in the listnums
. Ifv
is already innums
, the insertion point will be the index of the leftmostv
.
-
-
Index Checking and Result Collection: After finding the insertion points using binary search, we must ensure these indices are valid (i.e., within the range of the list). If they're valid, we retrieve the corresponding values as our
min_i
andmax_i
. If an index is out of bounds, it implies no such value exists in the BST, and we add-1
for that particular bound (eithermin_i
ormax_i
). We append these pairs[min_i, max_i]
to our answer for each query. -
Final Output: After iterating through all queries, our
answer
list contains the pairs for each query in accordance to the rules provided by the problem statement.
The data structures used in this approach are:
- A list
nums
to hold the in-order traversal of the BST values. - A list
ans
oranswer
that accumulates the pairs[min_i, max_i]
for each query.
The algorithms and patterns used are:
- In-Order Traversal: This recursive pattern is used to traverse and collect values from the BST in sorted order.
- Binary Search: This algorithm is used (with the help of the
bisect
module) to efficiently find the indices that will help derivemin_i
andmax_i
for each query.
This approach leverages the efficiencies of binary search trees and binary search algorithms to minimize the time complexity of searching for nearest values for a series of queries.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's say we have the following BST and a query list [7, 15, 3]
:
1 10 2 / \ 3 5 15 4 / \ \ 5 3 7 17
To answer the queries according to the provided solution approach, we'll follow these steps:
-
Perform in-order traversal of the BST:
First, we visit the leftmost node (3), then its parent (5), its right sibling (7), and so on, until we've visited all nodes. This will give us
nums = [3, 5, 7, 10, 15, 17]
. -
For each query value
v
, findmin_i
andmax_i
using binary search. Let's start with the first query7
:-
Using binary search to find
min_i
: We find the insertion point of7
. Since7
is in the list, the insertion point is to its right. We step back one index and find thatmin_i
is itself7
. -
Using binary search to find
max_i
: We find the insertion point for7
. Since7
is in the list,max_i
is also7
.
Thus, the answer to the first query is
[7, 7]
. -
-
Repeat for the second query,
15
:-
min_i
search: The insertion point for15
would be its own position, so stepping one index back gives us10
. However, since15
is in the list,min_i
is15
. -
max_i
search: The insertion point for15
is its own index, somax_i
is15
.
Therefore, the answer to the second query is
[15, 15]
. -
-
Finally, for the third query,
3
:-
min_i
search: Since3
is the first element in our list, we cannot step back, which means there is no smaller value. Hence,min_i
is3
. -
max_i
search: The insertion point for3
is at its own position, somax_i
is3
.
Hence, the answer to the third query is
[3, 3]
. -
-
Compile the final
answer
after evaluating all queries:The
answer
array accumulates the result for each query consecutively. As such, we getanswer = [[7, 7], [15, 15], [3, 3]]
.
Following the described solution approach, using the in-order traversal list, nums
, and binary search operations for both min_i
and max_i
, we were able to derive the closest values from the BST for each query efficiently.
Solution Implementation
1from bisect import bisect_left, bisect_right
2from typing import List, Optional
3
4# Definition for a binary tree node.
5class TreeNode:
6 def __init__(self, val=0, left=None, right=None):
7 self.val = val
8 self.left = left
9 self.right = right
10
11class Solution:
12 def closest_nodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
13 # Helper function to perform in-order traversal of the binary tree
14 # and collect the node values in a sorted list.
15 def inorder_traversal(node):
16 if node is None:
17 return
18 inorder_traversal(node.left) # Traverse left subtree
19 sorted_values.append(node.val) # Visit/Process the node
20 inorder_traversal(node.right) # Traverse right subtree
21
22 # Start in-order traversal and initialize the list to hold sorted node values
23 sorted_values = []
24 inorder_traversal(root)
25
26 # Initialize the list to hold the answer for each query
27 answer = []
28
29 # Process each query to find the closest nodes
30 for value in queries:
31 # Use binary search to find the insert position for the query value
32 right_index = bisect_left(sorted_values, value)
33 left_index = right_index - 1
34
35 # Get the closest value on the left, if available
36 left_val = sorted_values[left_index] if 0 <= left_index < len(sorted_values) else -1
37
38 # Get the closest value on the right, if available
39 right_val = sorted_values[right_index] if 0 <= right_index < len(sorted_values) else -1
40
41 # Append the closest values found to the answer list
42 answer.append([left_val, right_val])
43
44 # Return the list of answers for all queries
45 return answer
46
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5// Definition for a binary tree node.
6class TreeNode {
7 int val;
8 TreeNode left;
9 TreeNode right;
10
11 TreeNode() {}
12
13 TreeNode(int val) {
14 this.val = val;
15 }
16
17 TreeNode(int val, TreeNode left, TreeNode right) {
18 this.val = val;
19 this.left = left;
20 this.right = right;
21 }
22}
23
24class Solution {
25 // Store the sorted values of the tree
26 private List<Integer> sortedValues = new ArrayList<>();
27
28 /**
29 * Returns the closest node values from the tree for each query.
30 *
31 * @param root The root node of the binary tree.
32 * @param queries A list of integer queries.
33 * @return A list of lists, where each list contains two values (previous and next closest).
34 */
35 public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
36 // Perform an in-order traversal to get the sorted values of the binary search tree.
37 inOrderTraversal(root);
38
39 // Prepare the list to hold the answer.
40 List<List<Integer>> answer = new ArrayList<>();
41
42 // Iterate over each query to find closest values.
43 for (int queryValue : queries) {
44 // The predecessor index (closest smaller or equal value).
45 int predecessorIndex = binarySearch(queryValue + 1) - 1;
46 // The successor index (closest larger value).
47 int successorIndex = binarySearch(queryValue);
48 // The predecessor value, or -1 if there isn't one.
49 Integer predecessor = predecessorIndex >= 0 && predecessorIndex < sortedValues.size() ? sortedValues.get(predecessorIndex) : -1;
50 // The successor value, or -1 if there isn't one.
51 Integer successor = successorIndex >= 0 && successorIndex < sortedValues.size() ? sortedValues.get(successorIndex) : -1;
52 // Add the pair (predecessor, successor) to the answer.
53 answer.add(Arrays.asList(predecessor, successor));
54 }
55 return answer;
56 }
57
58 /**
59 * Performs a binary search to find the index of the smallest value greater than or equal to x.
60 *
61 * @param target The target value to search for.
62 * @return The index of the target value or the index where it should be placed.
63 */
64 private int binarySearch(int target) {
65 int left = 0, right = sortedValues.size();
66 while (left < right) {
67 int mid = (left + right) >> 1; // Equivalent to dividing by 2.
68 if (sortedValues.get(mid) >= target) {
69 right = mid;
70 } else {
71 left = mid + 1;
72 }
73 }
74 return left;
75 }
76
77 /**
78 * Performs an in-order traversal of the tree storing the elements in a sorted list.
79 *
80 * @param node The current node of the tree.
81 */
82 private void inOrderTraversal(TreeNode node) {
83 if (node == null) {
84 return;
85 }
86 // First, visit the left subtree.
87 inOrderTraversal(node.left);
88 // Then, visit the current node.
89 sortedValues.add(node.val);
90 // Finally, visit the right subtree.
91 inOrderTraversal(node.right);
92 }
93}
94
1// Definition for a binary tree node.
2struct TreeNode {
3 int val;
4 TreeNode *left;
5 TreeNode *right;
6 // Constructor for creating a new node with no children.
7 TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 // Constructor for creating a new node with a given value with no children.
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10 // Constructor for creating a new node with a value and specified left and right children.
11 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16 vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
17 // This vector will store the in-order traversal of the tree, which
18 // gives us the elements in ascending order.
19 vector<int> inorderTraversal;
20 // Recursive lambda function to perform in-order DFS traversal.
21 function<void(TreeNode*)> dfs = [&](TreeNode* node) {
22 if (!node) return;
23 dfs(node->left);
24 inorderTraversal.emplace_back(node->val);
25 dfs(node->right);
26 };
27 // Perform the in-order traversal starting from the root.
28 dfs(root);
29
30 // This vector will hold the final results.
31 vector<vector<int>> results;
32 int n = inorderTraversal.size();
33 // Go through each query to find the closest nodes
34 for (int& value : queries) {
35 // Find the first number that is greater than the query value.
36 int upperIndex = upper_bound(inorderTraversal.begin(), inorderTraversal.end(), value) - inorderTraversal.begin() - 1;
37 // Find the first number that is not less than the query value.
38 int lowerIndex = lower_bound(inorderTraversal.begin(), inorderTraversal.end(), value) - inorderTraversal.begin();
39
40 // Check if the 'upperIndex' is within the bounds of 'inorderTraversal'.
41 int closerLowerValue = upperIndex >= 0 && upperIndex < n ? inorderTraversal[upperIndex] : -1;
42 // Check if the 'lowerIndex' is within the bounds of 'inorderTraversal'.
43 int closerUpperValue = lowerIndex >= 0 && lowerIndex < n ? inorderTraversal[lowerIndex] : -1;
44
45 // Store the result for the current query.
46 results.push_back({closerLowerValue, closerUpperValue});
47 }
48 // Return the list of closest node values for each query.
49 return results;
50 }
51};
52
1// TypeScript types for the TreeNode structure and the Solution's methods.
2
3// Binary tree node structure definition.
4interface TreeNode {
5 val: number;
6 left: TreeNode | null;
7 right: TreeNode | null;
8}
9
10// Function to perform an in-order traversal of a binary tree
11// starting from the given root.
12function inorderTraversal(root: TreeNode | null): number[] {
13 const result: number[] = [];
14 const traverse = (node: TreeNode | null) => {
15 if (node === null) return;
16 traverse(node.left);
17 result.push(node.val);
18 traverse(node.right);
19 };
20 traverse(root);
21 return result;
22}
23
24// Function to find the closest nodes for each query from the given binary tree.
25function closestNodes(root: TreeNode | null, queries: number[]): number[][] {
26 // Perform the in-order traversal to get elements in sorted (ascending) order.
27 const traversalResult: number[] = inorderTraversal(root);
28
29 // This array will hold the final results.
30 const results: number[][] = [];
31 const length: number = traversalResult.length;
32
33 // For each query, find the closest nodes.
34 queries.forEach((value) => {
35 // Find the index of the first number greater than the query value.
36 const upperIndex = binarySearchUpper(traversalResult, value);
37 // Find the index of the first number not less than the query value.
38 const lowerIndex = binarySearchLower(traversalResult, value);
39
40 // Compute the values closest to the query.
41 const closerLowerValue = upperIndex > 0 && upperIndex < length ? traversalResult[upperIndex - 1] : -1;
42 const closerUpperValue = lowerIndex >= 0 && lowerIndex < length ? traversalResult[lowerIndex] : -1;
43
44 // Store the result for the current query.
45 results.push([closerLowerValue, closerUpperValue]);
46 });
47
48 // Return the list of closest node values for each query.
49 return results;
50}
51
52// Helper function for binary search to find the upper bound index.
53function binarySearchUpper(arr: number[], target: number): number {
54 let low = 0;
55 let high = arr.length;
56 while (low < high) {
57 let mid = Math.floor((low + high) / 2);
58 if (arr[mid] > target) {
59 high = mid;
60 } else {
61 low = mid + 1;
62 }
63 }
64 return low;
65}
66
67// Helper function for binary search to find the lower bound index.
68function binarySearchLower(arr: number[], target: number): number {
69 let low = 0;
70 let high = arr.length;
71 while (low < high) {
72 let mid = Math.floor((low + high) / 2);
73 if (arr[mid] < target) {
74 low = mid + 1;
75 } else {
76 high = mid;
77 }
78 }
79 return low;
80}
81
Time and Space Complexity
Time Complexity
The time complexity of the function is determined by several components:
-
Depth-First Search (DFS) for In-Order Traversal: The function
dfs
performs an in-order traversal of the binary tree to get a sorted list of all node values innums
. This step visits each node exactly once. Therefore, if the tree hasn
nodes, the complexity isO(n)
. -
Binary Search for Each Query: For each query value in
queries
, thebisect_right
andbisect_left
functions from thebisect
module are used to find the closest nodes. Both functions perform a binary search on the sorted listnums
, which has a time complexity ofO(log n)
per search.
Given that there are q
queries, the total time complexity for all binary searches combined is O(q log n)
.
Combining these two parts, the overall time complexity is O(n + q log n)
.
Space Complexity
The space complexity of the function also consists of multiple parts:
-
Space for Storing Node Values (
nums
): The in-order traversal stores all node values in the listnums
, so it usesO(n)
space. -
Recursive Stack Space: In the worst case (a completely unbalanced tree), the dfs recursion can go up to
n
deep, leading to a space complexity ofO(n)
. -
Space for Answer List (
ans
): The listans
that stores the results for each query is sized according to the number of queries, which isq
. Thus, it contributes an additionalO(q)
space.
The combined space complexity is dominated by the larger of O(n)
and O(q)
, which is O(n + q)
because we have to store each separately.
In summary:
- Time Complexity:
O(n + q log n)
- Space Complexity:
O(n + q)
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following uses divide and conquer strategy?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at