Skip to main content
Talentd

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

MediumArrayBinary SearchTreeDepth-First Search22 min readAsked at: Google
Practice this problem

Problem Statement

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.

 

Example 1:

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:

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 <= 106
  • n == queries.length
  • 1 <= n <= 105
  • 1 <= queries[i] <= 106

Approach Overview

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.

Approach 1: In-order Traversal and Binary Search

This approach involves performing an in-order traversal of the BST to acquire a sorted list of all node values. An in-order traversal naturally provides the values in ascending order for a BST.

Once we have the sorted list of values, we can use binary search to effectively find the closest values for each query. We look for the largest value smaller or equal (MIN) and the smallest value larger or equal (MAX) using binary search.

The C solution involves creating an additional space to store the sorted node values from an in-order traversal. We then apply binary search to find the closest values for each query in O(log n) time, making the overall solution efficient.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m log n), where n is the number of nodes in the tree and m is the number of queries.

Space Complexity: O(n) due to the storage of sorted node values.

Try this approach in the editor β†’

Approach 2: Recursive Query Processing without Additional Inorder List

This approach deals directly with recursive traversals of the tree for each query. For each query, position ourselves at the root, and move left if the query value is less than the current node, right otherwise, updating potential candidate values as needed to determine closest lower and upper values.

The C implementation handles each query via recursive calls traversing the tree. It keeps track of potential min and max values as it traverses left or right to efficiently resolve each query.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(h) per query, where h is the height of the tree, resulting in O(m * h) in total.

Space Complexity: O(h) for recursion stack.

Try this approach in the editor β†’

Approach 3: In-order Traversal + Binary Search

Since the problem provides a binary search tree, we can obtain a sorted array through in-order traversal. Then for each query, we can find the maximum value less than or equal to the query value and the minimum value greater than or equal to the query value through binary search.

The time complexity is O(n + m times log n), and the space complexity is O(n). Here, n and m are the number of nodes in the binary search tree and the number of queries, respectively.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
In-order Traversal and Binary Search

Time Complexity: O(n + m log n), where n is the number of nodes in the tree and m is the number of queries.

Space Complexity: O(n) due to the storage of sorted node values.

Recursive Query Processing without Additional Inorder List

Time Complexity: O(h) per query, where h is the height of the tree, resulting in O(m * h) in total.

Space Complexity: O(h) for recursion stack.

In-order Traversal + Binary Searchβ€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
In-order Traversal + Binary SearchO(n + q log n)O(n)Best when there are many queries and you want fast lookups after preprocessing
Direct BST Traversal per QueryO(q * h) (O(q log n) average, O(qn) worst)O(h)When you want to avoid extra memory or when the tree height is small

Video Solution

θŠ±θŠ±ι…± LeetCode 2476. Closest Nodes Queries in a Binary Search Tree - εˆ·ι’˜ζ‰Ύε·₯作 EP405 β€’ Hua Hua β€’ 1,931 views views

Watch 9 more video solutions β†’

Frequently Asked Questions

Is Closest Nodes Queries in a Binary Search Tree easy or hard?
Closest Nodes Queries in a Binary Search Tree is rated Medium difficulty on LeetCode with an acceptance rate around 44%. The challenge comes from efficiently answering multiple queries and correctly computing floor and ceiling values using BST properties.
Closest Nodes Queries in a Binary Search Tree Python/Java solution
Python and Java implementations typically follow the inorder traversal plus binary search approach. First collect all node values in sorted order using DFS. Then use a binary search function (like bisect in Python or Collections.binarySearch in Java) to locate the closest floor and ceiling values for each query.
How to solve Closest Nodes Queries in a Binary Search Tree in O(n)?
The tree preprocessing step can be done in O(n) using inorder traversal, which collects all node values in sorted order. After that, each query is handled using binary search to find the floor and ceiling. While the full query processing becomes O(n + q log n), the tree processing itself is linear.
What is the best approach for Closest Nodes Queries in a Binary Search Tree?
The most reliable approach performs an inorder traversal to convert the BST into a sorted array, then answers each query using binary search. This works because inorder traversal of a BST produces values in ascending order. The preprocessing takes O(n) time and each query takes O(log n), giving total complexity of O(n + q log n).
Is Closest Nodes Queries in a Binary Search Tree asked at Google/Amazon/Meta?
Binary search tree query problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations often involve finding predecessors, successors, floor/ceil values, or handling multiple queries efficiently. This problem tests understanding of BST ordering and efficient search strategies.
What data structure is used in Closest Nodes Queries in a Binary Search Tree?
The primary data structure is a Binary Search Tree (BST). Many solutions also convert the BST into a sorted array using inorder traversal, then apply binary search to answer queries efficiently. Depth-first search is used to perform the traversal.
What is the time complexity of Closest Nodes Queries in a Binary Search Tree?
The optimal preprocessing approach runs in O(n + q log n) time, where n is the number of nodes and q is the number of queries. Building the sorted list via inorder traversal takes O(n), and each query uses binary search in O(log n). The space complexity is O(n) for storing the node values.

Ready to solve this problem?

Practice Closest Nodes Queries in a Binary Search Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Closest Binary Search Tree Value

Next

Closest Binary Search Tree Value II