Closest Nodes Queries in a Binary Search Tree
MedPrompt
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]:
miniis the largest value in the tree that is smaller than or equal toqueries[i]. If a such value does not exist, add-1instead.maxiis the smallest value in the tree that is greater than or equal toqueries[i]. If a such value does not exist, add-1instead.
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:
- The number of nodes in the tree is in the range
[2, 105]. 1 <= Node.val <= 106n == queries.length1 <= n <= 1051 <= queries[i] <= 106
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to handle each query independently. For every integer in the queries list, we can traverse the entire binary search tree to find the required min_i and max_i values. This method does not utilize the sorted nature of the BST.
Algorithm
- Initialize an empty list
answer. - Iterate through each
queryin thequerieslist. - For each
query, initializemin_i = -1andmax_i = -1. - Perform a full traversal of the tree (e.g., using an iterative DFS with a stack).
- For each
nodevisited:- Update
min_i:min_i = max(min_i, node.val)ifnode.val <= query. - Update
max_i: Ifnode.val >= query, updatemax_ito benode.valifmax_iis-1ornode.val < max_i.
- Update
- After the traversal, add the pair
[min_i, max_i]toanswer. - Return
answer.
Walkthrough
For each query, we initialize min_i to -1 and max_i to -1. We then perform a full traversal of the tree (using either Depth-First Search or Breadth-First Search). During the traversal, for each node, we compare its value with the current query value.
- If
node.val <= query, it's a candidate formin_i. We updatemin_iif thisnode.valis larger than the currentmin_i. - If
node.val >= query, it's a candidate formax_i. We updatemax_iif thisnode.valis smaller than the currentmax_i(or ifmax_iis still -1). After checking all nodes, the finalmin_iandmax_iare the answer for that query. This process is repeated for all queries.
import java.util.*; class Solution { public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) { List<List<Integer>> answer = new ArrayList<>(); for (int query : queries) { int minVal = -1; int maxVal = -1; Stack<TreeNode> stack = new Stack<>(); if (root != null) { stack.push(root); } while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node.val <= query) { minVal = Math.max(minVal, node.val); } if (node.val >= query) { if (maxVal == -1 || node.val < maxVal) { maxVal = node.val; } } if (node.left != null) stack.push(node.left); if (node.right != null) stack.push(node.right); } answer.add(Arrays.asList(minVal, maxVal)); } return answer; }}Complexity
Time
O(M * N), where `M` is the number of queries and `N` is the number of nodes in the tree. For each of the `M` queries, we traverse all `N` nodes.
Space
O(H), where `H` is the height of the tree. The space is used for the traversal stack. In the worst case of a skewed tree, this becomes O(N).
Trade-offs
Pros
Conceptually simple and easy to implement.
Cons
Extremely inefficient. It completely ignores the properties of a Binary Search Tree.
Will result in a 'Time Limit Exceeded' error for the given constraints.
A better approach is to leverage the fundamental property of a Binary Search Tree (BST). For any given node, all values in its left subtree are smaller, and all values in its right subtree are larger. This allows us to avoid a full tree traversal for each query by performing a targeted search.
Algorithm
- Initialize an empty list
answer. - Iterate through each
queryin thequerieslist. - For each
query, findmin_iandmax_iby searching the BST.- To find
min_i(floor):- Start at the
root, initializemin_i = -1. - While the current node is not null:
- If
node.val == query,min_iisquery, break. - If
node.val < query, it's a candidate. Setmin_i = node.valand move to the right child. - If
node.val > query, move to the left child.
- If
- Start at the
- To find
max_i(ceiling):- Start at the
root, initializemax_i = -1. - While the current node is not null:
- If
node.val == query,max_iisquery, break. - If
node.val > query, it's a candidate. Setmax_i = node.valand move to the left child. - If
node.val < query, move to the right child.
- If
- Start at the
- To find
- Add the pair
[min_i, max_i]toanswer. - Return
answer.
Walkthrough
For each query, we can perform two separate searches on the BST, both starting from the root.
- To find
min_i(the floor): We traverse the tree. If the current node's value is equal to the query, we've found the exact value. If it's less than the query, it's a potential candidate formin_i, so we record it and move to the right subtree to find a potentially larger value that is still smaller than the query. If the node's value is greater than the query, we move to the left subtree. - To find
max_i(the ceiling): The logic is symmetric. If the current node's value is greater than the query, it's a potentialmax_i. We record it and move to the left subtree to find a potentially smaller value that is still larger than the query. If the node's value is less than the query, we move to the right subtree. This process is repeated for every query.
import java.util.*; class Solution { public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) { List<List<Integer>> answer = new ArrayList<>(); for (int query : queries) { answer.add(findClosestPair(root, query)); } return answer; } private List<Integer> findClosestPair(TreeNode root, int query) { int minVal = -1; int maxVal = -1; TreeNode current = root; while (current != null) { if (current.val == query) { minVal = current.val; break; } if (current.val < query) { minVal = current.val; current = current.right; } else { current = current.left; } } current = root; while (current != null) { if (current.val == query) { maxVal = current.val; break; } if (current.val > query) { maxVal = current.val; current = current.left; } else { current = current.right; } } return Arrays.asList(minVal, maxVal); }}Complexity
Time
O(M * H), where `M` is the number of queries and `H` is the height of the tree. In a balanced BST, `H` is `log(N)`, making the complexity O(M * log N). However, in a skewed tree, `H` can be `N`, leading to a worst-case complexity of O(M * N).
Space
O(1) if using an iterative search as shown. If a recursive approach is used, the space complexity would be O(H) for the recursion stack.
Trade-offs
Pros
Much more efficient than brute force for balanced or semi-balanced trees.
Directly utilizes the structure of the BST.
Cons
The performance is heavily dependent on the balance of the tree.
Can be as slow as the brute-force approach for skewed trees.
The most efficient and reliable approach involves decoupling the tree traversal from query processing. We can first flatten the BST into a sorted array of its values using an in-order traversal. Once we have this sorted array, finding the floor (min_i) and ceiling (max_i) for each query becomes a standard binary search problem.
Algorithm
- Create an empty list
sortedNodes. - Perform an in-order traversal of the BST, adding each node's value to
sortedNodes. This list will be sorted. - Initialize an empty list
answer. - Iterate through each
queryin thequerieslist.- Use binary search on
sortedNodesto find the floor and ceiling for the currentquery. - If the
queryvalue is found at indexidx, thenmin_iandmax_iare bothsortedNodes[idx]. - If the
queryis not found, the binary search will indicate aninsertionPoint.max_iis the element atinsertionPoint(if it's within the list bounds).min_iis the element atinsertionPoint - 1(if it's within the list bounds).
- Handle edge cases where a floor or ceiling does not exist.
- Add the found pair
[min_i, max_i]toanswer.
- Use binary search on
- Return
answer.
Walkthrough
The algorithm consists of two main phases:
- Preprocessing: Perform an in-order traversal (left, root, right) on the given BST. This traversal visits nodes in ascending order of their values. We store these values in a list, which will naturally be sorted.
- Query Processing: For each query, we use binary search on the sorted list to find the floor (
min_i) and ceiling (max_i). Many programming languages provide built-in functions for binary search that can simplify this. For example, in Java,Collections.binarySearchcan be used. It returns the index of the element if found, or-(insertion point) - 1if not found. From this information, we can easily deduce the indices of the floor and ceiling elements. This approach is efficient because the costly tree traversal is done only once, and each subsequent query is answered quickly using the highly optimized binary search algorithm.
import java.util.*; class Solution { public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) { List<Integer> sortedNodes = new ArrayList<>(); inorder(root, sortedNodes); List<List<Integer>> answer = new ArrayList<>(); int n = sortedNodes.size(); for (int query : queries) { int minVal = -1; int maxVal = -1; int idx = Collections.binarySearch(sortedNodes, query); if (idx >= 0) { minVal = sortedNodes.get(idx); maxVal = sortedNodes.get(idx); } else { int insertionPoint = -(idx + 1); if (insertionPoint < n) { maxVal = sortedNodes.get(insertionPoint); } if (insertionPoint > 0) { minVal = sortedNodes.get(insertionPoint - 1); } } answer.add(Arrays.asList(minVal, maxVal)); } return answer; } private void inorder(TreeNode node, List<Integer> list) { if (node == null) { return; } inorder(node.left, list); list.add(node.val); inorder(node.right, list); }}Complexity
Time
O(N + M * log N), where `N` is the number of nodes and `M` is the number of queries. The in-order traversal takes O(N) time. Then, for each of the `M` queries, we perform a binary search which takes O(log N) time.
Space
O(N) to store the `sortedNodes` list. An additional O(H) space is used for the recursion stack during the in-order traversal, which is at most O(N).
Trade-offs
Pros
Highly efficient and provides guaranteed performance regardless of the tree's structure.
The time complexity is optimal for the given problem constraints.
Cons
Requires O(N) extra space to store all the node values from the tree.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { private List < int > nums = new List < int >(); public IList < IList < int >> ClosestNodes ( TreeNode root , IList < int > queries ) { Dfs ( root ); List < IList < int >> ans = new List < IList < int >>(); foreach ( int x in queries ) { int i = nums . BinarySearch ( x + 1 ); int j = nums . BinarySearch ( x ); i = i < 0 ? - i - 2 : i - 1 ; j = j < 0 ? - j - 1 : j ; int mi = i >= 0 && i < nums . Count ? nums [ i ] : - 1 ; int mx = j >= 0 && j < nums . Count ? nums [ j ] : - 1 ; ans . Add ( new List < int > { mi , mx }); } return ans ; } private void Dfs ( TreeNode root ) { if ( root == null ) { return ; } Dfs ( root . left ); nums . Add ( root . val ); Dfs ( root . right ); } }/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private List < Integer > nums = new ArrayList <>(); public List < List < Integer >> closestNodes ( TreeNode root , List < Integer > queries ) { dfs ( root ); List < List < Integer >> ans = new ArrayList <>(); for ( int x : queries ) { int i = Collections . binarySearch ( nums , x + 1 ); int j = Collections . binarySearch ( nums , x ); i = i < 0 ? - i - 2 : i - 1 ; j = j < 0 ? - j - 1 : j ; int mi = i >= 0 && i < nums . size () ? nums . get ( i ) : - 1 ; int mx = j >= 0 && j < nums . size () ? nums . get ( j ) : - 1 ; ans . add ( List . of ( mi , mx )); } return ans ; } private void dfs ( TreeNode root ) { if ( root == null ) { return ; } dfs ( root . left ); nums . add ( root . val ); dfs ( root . right ); } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < vector < int >> closestNodes ( TreeNode * root , vector < int >& queries ) { vector < int > nums ; function < void ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) { if ( ! root ) { return ; } dfs ( root -> left ); nums . push_back ( root -> val ); dfs ( root -> right ); }; dfs ( root ); vector < vector < int >> ans ; int n = nums . size (); for ( int & x : queries ) { int i = lower_bound ( nums . begin (), nums . end (), x + 1 ) - nums . begin () - 1 ; int j = lower_bound ( nums . begin (), nums . end (), x ) - nums . begin (); int mi = i >= 0 && i < n ? nums [ i ] : - 1 ; int mx = j >= 0 && j < n ? nums [ j ] : - 1 ; ans . push_back ({ mi , mx }); } return ans ; } };# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def closestNodes ( self , root : Optional [ TreeNode ], queries : List [ int ] ) -> List [ List [ int ]]: def dfs ( root : Optional [ TreeNode ]): if root is None : return dfs ( root . left ) nums . append ( root . val ) dfs ( root . right ) nums = [] dfs ( root ) ans = [] for x in queries : i = bisect_left ( nums , x + 1 ) - 1 j = bisect_left ( nums , x ) mi = nums [ i ] if 0 <= i < len ( nums ) else - 1 mx = nums [ j ] if 0 <= j < len ( nums ) else - 1 ans . append ([ mi , mx ]) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.