Floor and Ceiling in a Search Tree

Medium

You are given the root of a binary search tree (every value in a node's left subtree is smaller than the node's value, every value in its right subtree is larger) and an array of numbers probes. For each number x in probes, find the pair [lo, hi]: - lo is the largest value in the tree that is at most x, or -1 if there is none; - hi is the smallest value in the tree that is at least x, or -1 if there is none. Return the list of pairs in the order of probes.

Example 1

root=tree_node([20, 10, 35, 5, 15, None, 50]), probes=[15, 27, 3, 60] → [[15, 15], [20, 35], [-1, 5], [50, -1]]

15 is in the tree, so [15, 15]. For 27 the closest value below is 20 and above is 35. Nothing in the tree is at most 3, and the closest above is 5. Nothing is at least 60.

Example 2

root=tree_node([7, None, 12]), probes=[9] → [[7, 12]]

9 falls between 7 and 12.

Constraints

2 ≤ number of nodes ≤ 10⁵
1 ≤ Node.val ≤ 10⁶
The tree is a valid search tree with distinct values
1 ≤ len(probes) ≤ 10⁵
1 ≤ probes[i] ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Binary Search Tree Array Binary Search Binary Tree

Similar problems

Pair Across Two Search Trees Medium Nearest Value in a Search Tree Easy Is It a Search Tree? Medium Two Mixed-Up Nodes Medium K-th Smallest in a Search Tree Medium

Input

root=tree_node([20, 10, 35, 5, 15, None, 50]), probes=[15, 27, 3, 60]

Expected

[[15, 15], [20, 35], [-1, 5], [50, -1]]

Run checks the first 3 tests in your browser. Submit checks all 29 tests on the server, hidden ones included.