# Closest Nodes Queries in a Binary Search Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/closest-nodes-queries-in-a-binary-search-tree)
Canonical: https://scaleengineer.com/dsa/problems/closest-nodes-queries-in-a-binary-search-tree
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, Tree, Binary Tree, Binary Search Tree
---
## Problem
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:**

![](https://assets.glich.co/dsa/closest-nodes-queries-in-a-binary-search-tree/image0.png) 

**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:**

![](https://assets.glich.co/dsa/closest-nodes-queries-in-a-binary-search-tree/image1.png) 

**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`

# Approaches
## Brute Force: Traverse Tree for Each Query
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.
**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).
**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.
### Explanation
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 for `min_i`. We update `min_i` if this `node.val` is larger than the current `min_i`.
- If `node.val >= query`, it's a candidate for `max_i`. We update `max_i` if this `node.val` is smaller than the current `max_i` (or if `max_i` is still -1).
After checking all nodes, the final `min_i` and `max_i` are the answer for that query. This process is repeated for all queries.
```java
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;
    }
}
```
### Algorithm
- Initialize an empty list `answer`.
- Iterate through each `query` in the `queries` list.
- For each `query`, initialize `min_i = -1` and `max_i = -1`.
- Perform a full traversal of the tree (e.g., using an iterative DFS with a stack).
- For each `node` visited:
  - Update `min_i`: `min_i = max(min_i, node.val)` if `node.val <= query`.
  - Update `max_i`: If `node.val >= query`, update `max_i` to be `node.val` if `max_i` is `-1` or `node.val < max_i`.
- After the traversal, add the pair `[min_i, max_i]` to `answer`.
- Return `answer`.

## BST Search for Each Query
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.
**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.
**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.
### Explanation
For each query, we can perform two separate searches on the BST, both starting from the root.
1.  **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 for `min_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.
2.  **To find `max_i` (the ceiling):** The logic is symmetric. If the current node's value is greater than the query, it's a potential `max_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.
```java
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);
    }
}
```
### Algorithm
- Initialize an empty list `answer`.
- Iterate through each `query` in the `queries` list.
- For each `query`, find `min_i` and `max_i` by searching the BST.
  - **To find `min_i` (floor):**
    - Start at the `root`, initialize `min_i = -1`.
    - While the current node is not null:
      - If `node.val == query`, `min_i` is `query`, break.
      - If `node.val < query`, it's a candidate. Set `min_i = node.val` and move to the right child.
      - If `node.val > query`, move to the left child.
  - **To find `max_i` (ceiling):**
    - Start at the `root`, initialize `max_i = -1`.
    - While the current node is not null:
      - If `node.val == query`, `max_i` is `query`, break.
      - If `node.val > query`, it's a candidate. Set `max_i = node.val` and move to the left child.
      - If `node.val < query`, move to the right child.
- Add the pair `[min_i, max_i]` to `answer`.
- Return `answer`.

## Efficient Approach: In-order Traversal and Binary Search
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.
**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).
**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.
### Explanation
The algorithm consists of two main phases:
1.  **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.
2.  **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.binarySearch` can be used. It returns the index of the element if found, or `-(insertion point) - 1` if 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.
```java
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);
    }
}
```
### 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 `query` in the `queries` list.
  - Use binary search on `sortedNodes` to find the floor and ceiling for the current `query`.
  - If the `query` value is found at index `idx`, then `min_i` and `max_i` are both `sortedNodes[idx]`.
  - If the `query` is not found, the binary search will indicate an `insertionPoint`.
    - `max_i` is the element at `insertionPoint` (if it's within the list bounds).
    - `min_i` is the element at `insertionPoint - 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]` to `answer`.
- Return `answer`.

# Solutions
### CSharp

```csharp
/** * 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 ); } }
```

### Java

```java
/** * 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 ); } }
```

### CPP

```cpp
/** * 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 ; } };
```

### Python

```python
# 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 ans
```