Closest Nodes Queries in a Binary Search Tree - Solution & Explanation

Problem Overview: Given the root of a binary search tree and multiple query values, return two numbers for each query: the largest value in the tree less than or equal to the query (floor) and the smallest value greater than or equal to it (ceiling). If either value doesn't exist, return -1. The BST property makes it possible to search efficiently.

Approach 1: In-order Traversal and Binary Search (Time: O(n + q log n), Space: O(n))

An in-order traversal of a BST produces a sorted array of node values. Traverse the tree once using depth-first search and store the values in a list. For each query, run binary search on the sorted list to locate the insertion position. The value at or before that index gives the floor, and the value at or after it gives the ceiling. This approach is straightforward and efficient when there are many queries because the tree is processed only once.

Approach 2: Recursive Query Processing without Additional Inorder List (Time: O(q * h), Space: O(h))

Instead of building a sorted list, process each query directly on the BST. Start from the root and move left or right depending on how the query compares to the current node value. Track two variables during traversal: the best candidate for floor and the best candidate for ceiling. Moving left updates the ceiling candidate; moving right updates the floor candidate. Because each query follows a single root-to-leaf path, the time per query is proportional to the tree height h. This avoids storing an extra array but may be slower if the tree is skewed.

Recommended for interviews: The in-order traversal with binary search is the most commonly expected solution. It clearly uses the BST property and reduces repeated work when handling many queries. Implementing the direct BST traversal approach shows deeper understanding of tree navigation and space optimization, but interviewers typically expect the sorted-array plus binary-search pattern first.