All problems

Floor and Ceiling in a BST

Medium · tree dfs

You are given the root of a binary search tree (BST) and a list of integers queries. For each query x, find two values from the tree:

If a query has no floor (every value is larger than x), its floor is -1. If it has no ceiling (every value is smaller than x), its ceiling is -1. This is safe because every value in the tree is non-negative. If x itself is in the tree, then both the floor and the ceiling are x.

Return a list with one pair [floor, ceiling] per query, in the same order as queries. The tree may be empty, in which case every pair is [-1, -1].

In a BST, for every node all values in its left subtree are smaller and all values in its right subtree are larger. All values are distinct.

Examples

Example 1

Input: root = [8, 3, 10, 1, 6, null, 14], queries = [5, 10, 0, 15]

Output: [[3, 6], [10, 10], [-1, 1], [14, -1]]

5 lies between 3 and 6. 10 is in the tree. 0 is below every value, so it has no floor. 15 is above every value, so it has no ceiling.

Example 2

Input: root = [4, 2, 6, 1, 3, 5, 7], queries = [4, 7]

Output: [[4, 4], [7, 7]]

Both queries are values in the tree, so each is its own floor and ceiling.

Example 3

Input: root = [], queries = [3]

Output: [[-1, -1]]

An empty tree has no values at all.

Constraints