Closest Nodes Queries in a Binary Search Tree
MediumArrayBinary SearchLinked ListTreeBinary Search TreeGraph
Description
Given a BST root and array of queries, for each query return the [floor, ceiling] pair from the tree, or -1 if not found.
Examples
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:
The BST property (left subtree < node < right subtree) enables efficient floor/ceiling searches in O(log n) time. When searching for a query value, traversing left updates the ceiling candidate and traversing right updates the floor candidate, since each direction narrows down to the closest bounding values.
Input:
root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [1]Output:
[[1,1]]Explanation:
Edge case with a single-element array.
Input:
root = [10,5,20,3,7,15,25,null,null,6,8], queries = [12,3,30]Output:
[[10,15],[3,3],[25,-1]]Explanation:
For query 12: closest smaller is 8, closest larger is 15. For query 3: the value 3 exists in BST, so both smaller and larger are 3. For query 30: closest smaller is 25, no larger value exists so -1.
Constraints
- •
2 ≤ nodes ≤ 10⁵