#2476

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Closest Nodes Queries in a Binary Search Tree

Solve the problem of finding closest nodes in a Binary Search Tree for multiple queries, efficiently handling each query with binary search techniques.

array binary search tree depth first search binary search tree

Problem Statement

Given the root of a Binary Search Tree and a list of queries, your task is to return a 2D array where each entry corresponds to a query, and contains two integers: the largest node value smaller or equal to the query, and the smallest node value greater or equal to the query. If no such value exists, return -1 for the respective value.

You can assume that the tree has at least two nodes and that the values of the queries are within a given range. You must optimize your solution to handle up to 100,000 queries and trees with up to 100,000 nodes. The challenge here is balancing the binary search and tree traversal techniques to efficiently find the answers for each query.

Examples

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]]

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]]

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

Solution Approach

Convert Tree to Sorted Array

Start by converting the Binary Search Tree into a sorted array of node values. This allows each query to be answered in logarithmic time using binary search techniques to find the closest nodes. A depth-first search (DFS) can be used to collect the values of the tree in sorted order.

Binary Search for Closest Values

For each query, perform a binary search on the sorted array of tree node values. Find the largest number smaller or equal to the query, and the smallest number greater or equal to the query. This can be done by tracking indices in the sorted array using binary search.

Handle Edge Cases

Ensure that the binary search handles edge cases like when no smaller value exists for a query, or when no larger value exists. In such cases, return -1 for the missing values. This ensures that every query has a valid response, even in cases where one of the closest values doesn't exist.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution depends on converting the tree to a sorted array, which takes O(n) where n is the number of nodes in the tree. For each query, binary search takes O(log n). Thus, the overall time complexity for processing q queries is O(n + q log n). The space complexity is O(n) to store the sorted node values.

What Interviewers Usually Probe

The candidate efficiently handles large inputs by reducing the problem to binary search on a sorted array.
Look for correct handling of edge cases, especially the absence of a larger or smaller value for a query.
The candidate demonstrates a solid understanding of binary search tree traversal and its application to solve problems efficiently.

Common Pitfalls or Variants

Common pitfalls

Failing to optimize the solution for large inputs, resulting in a slower approach for processing the tree or queries.
Incorrectly handling edge cases like when no smaller or larger node value exists for a query.
Not converting the tree into a sorted array, leading to inefficient queries and unnecessary repeated traversal of the tree.

Follow-up variants

What if the queries are given in random order, should the approach be adjusted to handle this?
Consider a version where the tree is dynamic and can be updated between queries. How would that affect the solution?
What if you have multiple trees and need to process queries for each one separately?

FAQ

What is the best way to handle large inputs in this problem?

The best approach is to first convert the Binary Search Tree into a sorted array, allowing each query to be answered in O(log n) time using binary search.

How do I handle queries where no smaller or larger value exists in the tree?

In such cases, return -1 for the missing value. Ensure the binary search algorithm accounts for these edge cases.

Is there a way to optimize the tree traversal for larger trees?

Yes, by converting the tree into a sorted array using a depth-first traversal (DFS), you can avoid repeated tree traversal for each query.

What is the time complexity of this problem?

The time complexity is O(n + q log n), where n is the number of nodes in the tree and q is the number of queries.

How do I approach this problem if the tree can be updated between queries?

If the tree is dynamic, you will need to update the sorted array as nodes are added or removed, and adjust the binary search accordingly.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def closestNodes(
        self, root: Optional[TreeNode], queries: List[int]
    ) -> List[List[int]]:
        def dfs(root: Optional[TreeNode]):
            if root is None:
                return
            dfs(root.left)
            nums.append(root.val)
            dfs(root.right)

        nums = []
        dfs(root)
        ans = []
        for x in queries:
            i = bisect_left(nums, x + 1) - 1
            j = bisect_left(nums, x)
            mi = nums[i] if 0 <= i < len(nums) else -1
            mx = nums[j] if 0 <= j < len(nums) else -1
            ans.append([mi, mx])
        return ans

Continue Practicing

#2458 height of binary tree after subtree removal queries #2049 count nodes with the highest score #1932 merge bsts to create single bst