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.

Examples

Example 1

1
2
3
4
5
6
7
8
9


![](https://assets.leetcode.com/uploads/2022/09/28/bstreeedrawioo.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

1
2
3
4
5
6


![](https://assets.leetcode.com/uploads/2022/09/28/bstttreee.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 <= 10^6
  • n == queries.length
  • 1 <= n <= 10^5
  • 1 <= queries[i] <= 10^6

Solution

Method 1 – Inorder Traversal + Binary Search

Intuition

A binary search tree’s inorder traversal yields a sorted list of values. For each query, we can use binary search on this sorted list to efficiently find the largest value ≤ query and the smallest value ≥ query.

Approach

  1. Traverse the BST in inorder to collect all values in a sorted array.
  2. For each query:
    • Use binary search to find the rightmost value ≤ query (for mini).
    • Use binary search to find the leftmost value ≥ query (for maxi).
    • If such values do not exist, use -1.
  3. Return the answer for all queries.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    void inorder(TreeNode* root, vector<int>& vals) {
        if (!root) return;
        inorder(root->left, vals);
        vals.push_back(root->val);
        inorder(root->right, vals);
    }
    vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
        vector<int> vals;
        inorder(root, vals);
        vector<vector<int>> ans;
        for (int q : queries) {
            auto it1 = upper_bound(vals.begin(), vals.end(), q);
            int mini = (it1 == vals.begin()) ? -1 : *(--it1);
            auto it2 = lower_bound(vals.begin(), vals.end(), q);
            int maxi = (it2 == vals.end()) ? -1 : *it2;
            ans.push_back({mini, maxi});
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

type TreeNode struct {
    Val int
    Left, Right *TreeNode
}
func closestNodes(root *TreeNode, queries []int) [][]int {
    var vals []int
    var inorder func(*TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil { return }
        inorder(node.Left)
        vals = append(vals, node.Val)
        inorder(node.Right)
    }
    inorder(root)
    ans := make([][]int, len(queries))
    for i, q := range queries {
        mini, maxi := -1, -1
        l, r := 0, len(vals)-1
        for l <= r {
            m := (l + r) / 2
            if vals[m] <= q {
                mini = vals[m]
                l = m + 1
            } else {
                r = m - 1
            }
        }
        l, r = 0, len(vals)-1
        for l <= r {
            m := (l + r) / 2
            if vals[m] >= q {
                maxi = vals[m]
                r = m - 1
            } else {
                l = m + 1
            }
        }
        ans[i] = []int{mini, maxi}
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    List<Integer> vals = new ArrayList<>();
    void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        vals.add(root.val);
        inorder(root.right);
    }
    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        inorder(root);
        List<List<Integer>> ans = new ArrayList<>();
        for (int q : queries) {
            int mini = -1, maxi = -1;
            int l = 0, r = vals.size() - 1;
            while (l <= r) {
                int m = (l + r) / 2;
                if (vals.get(m) <= q) {
                    mini = vals.get(m);
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            l = 0; r = vals.size() - 1;
            while (l <= r) {
                int m = (l + r) / 2;
                if (vals.get(m) >= q) {
                    maxi = vals.get(m);
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
            ans.add(Arrays.asList(mini, maxi));
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    fun closestNodes(root: TreeNode?, queries: List<Int>): List<List<Int>> {
        val vals = mutableListOf<Int>()
        fun inorder(node: TreeNode?) {
            if (node == null) return
            inorder(node.left)
            vals.add(node.`val`)
            inorder(node.right)
        }
        inorder(root)
        return queries.map { q ->
            var mini = -1; var maxi = -1
            var l = 0; var r = vals.size - 1
            while (l <= r) {
                val m = (l + r) / 2
                if (vals[m] <= q) { mini = vals[m]; l = m + 1 } else { r = m - 1 }
            }
            l = 0; r = vals.size - 1
            while (l <= r) {
                val m = (l + r) / 2
                if (vals[m] >= q) { maxi = vals[m]; r = m - 1 } else { l = m + 1 }
            }
            listOf(mini, maxi)
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    def closestNodes(self, root: 'TreeNode', queries: list[int]) -> list[list[int]]:
        vals = []
        def inorder(node):
            if not node: return
            inorder(node.left)
            vals.append(node.val)
            inorder(node.right)
        inorder(root)
        ans = []
        for q in queries:
            mini, maxi = -1, -1
            l, r = 0, len(vals) - 1
            while l <= r:
                m = (l + r) // 2
                if vals[m] <= q:
                    mini = vals[m]
                    l = m + 1
                else:
                    r = m - 1
            l, r = 0, len(vals) - 1
            while l <= r:
                m = (l + r) // 2
                if vals[m] >= q:
                    maxi = vals[m]
                    r = m - 1
                else:
                    l = m + 1
            ans.append([mini, maxi])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

impl Solution {
    pub fn closest_nodes(root: Option<Rc<RefCell<TreeNode>>>, queries: Vec<i32>) -> Vec<Vec<i32>> {
        fn inorder(node: Option<Rc<RefCell<TreeNode>>>, vals: &mut Vec<i32>) {
            if let Some(n) = node {
                inorder(n.borrow().left.clone(), vals);
                vals.push(n.borrow().val);
                inorder(n.borrow().right.clone(), vals);
            }
        }
        let mut vals = vec![];
        inorder(root, &mut vals);
        let mut ans = vec![];
        for q in queries {
            let (mut mini, mut maxi) = (-1, -1);
            let (mut l, mut r) = (0, vals.len() as i32 - 1);
            while l <= r {
                let m = (l + r) / 2;
                if vals[m as usize] <= q {
                    mini = vals[m as usize];
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            l = 0; r = vals.len() as i32 - 1;
            while l <= r {
                let m = (l + r) / 2;
                if vals[m as usize] >= q {
                    maxi = vals[m as usize];
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
            ans.push(vec![mini, maxi]);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    closestNodes(root: TreeNode | null, queries: number[]): number[][] {
        const vals: number[] = [];
        function inorder(node: TreeNode | null) {
            if (!node) return;
            inorder(node.left);
            vals.push(node.val);
            inorder(node.right);
        }
        inorder(root);
        return queries.map(q => {
            let mini = -1, maxi = -1;
            let l = 0, r = vals.length - 1;
            while (l <= r) {
                const m = (l + r) >> 1;
                if (vals[m] <= q) { mini = vals[m]; l = m + 1; } else { r = m - 1; }
            }
            l = 0; r = vals.length - 1;
            while (l <= r) {
                const m = (l + r) >> 1;
                if (vals[m] >= q) { maxi = vals[m]; r = m - 1; } else { l = m + 1; }
            }
            return [mini, maxi];
        });
    }
}

Complexity

  • ⏰ Time complexity: O(n + q log n), where n is the number of nodes and q is the number of queries.
  • 🧺 Space complexity: O(n)