Problem Description

You have a binary search tree and need to find the closest values for multiple queries.

Given:

• The root of a binary search tree
• An array queries containing n positive integers

For each query value in queries[i], you need to find two values from the tree:

1. The floor value (min_i): The largest value in the tree that is less than or equal to queries[i]. If no such value exists, use -1.

2. The ceiling value (max_i): The smallest value in the tree that is greater than or equal to queries[i]. If no such value exists, use -1.

Return a 2D array answer where each answer[i] = [min_i, max_i] corresponds to the floor and ceiling values for queries[i].

Example walkthrough: If the BST contains values [1, 4, 6, 9] and you query for 5:

• The floor (largest value ≤ 5) would be 4
• The ceiling (smallest value ≥ 5) would be 6
• Result: [4, 6]

If you query for 10 in the same tree:

• The floor (largest value ≤ 10) would be 9
• The ceiling (smallest value ≥ 10) doesn't exist, so it's -1
• Result: [9, -1]

The solution leverages the BST property by performing an in-order traversal to get a sorted array of all values, then uses binary search (bisect_left) to efficiently find the floor and ceiling values for each query.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary search tree is a special type of graph where each node has at most two children (left and right), forming a hierarchical structure with nodes and edges.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary search tree, which is a tree data structure.

DFS

• Result: Based on the flowchart, when we have a tree structure, the algorithm directs us to use DFS (Depth-First Search).

Conclusion: The flowchart suggests using DFS for this problem. This aligns perfectly with the solution approach, which uses DFS (specifically, in-order traversal) to traverse the binary search tree and extract all values in sorted order. The DFS traversal visits nodes recursively by going deep into the left subtree first, then processing the current node, and finally traversing the right subtree. This in-order DFS traversal of a BST naturally gives us a sorted array, which can then be used with binary search to efficiently answer the queries for floor and ceiling values.

Intuition

The key insight is recognizing that a binary search tree has a special property: an in-order traversal always gives us values in sorted order. This is because in a BST, all values in the left subtree are smaller than the root, and all values in the right subtree are larger than the root.

When we need to find the floor (largest value ≤ query) and ceiling (smallest value ≥ query) for multiple queries, we could traverse the tree for each query separately. However, this would be inefficient, especially with many queries.

Instead, we can leverage the BST's sorted property. By performing a single DFS in-order traversal upfront, we extract all values into a sorted array. This transforms our tree search problem into an array search problem.

Once we have a sorted array, finding floor and ceiling values becomes a classic binary search problem:

• For the floor value: We need to find the rightmost element that is ≤ the query value
• For the ceiling value: We need to find the leftmost element that is ≥ the query value

The bisect_left function helps us here. For a query value x:

• bisect_left(nums, x) gives us the index where x would be inserted to keep the array sorted - this is exactly the ceiling position
• bisect_left(nums, x + 1) - 1 gives us the index of the largest value ≤ x - this is the floor position

This approach is efficient because we traverse the tree only once (O(n) time) and then each query takes only O(log n) time using binary search, rather than traversing the tree for each query which would take O(n * q) time where q is the number of queries.

Learn more about Tree, Depth-First Search, Binary Search Tree, Binary Search and Binary Tree patterns.

Solution Approach

The solution follows a two-phase approach: first extracting values from the BST, then efficiently answering queries.

Phase 1: Extract Values using DFS In-order Traversal

We implement a recursive DFS function that performs in-order traversal:

def dfs(root: Optional[TreeNode]):
    if root is None:
        return
    dfs(root.left)    # Visit left subtree
    nums.append(root.val)  # Process current node
    dfs(root.right)   # Visit right subtree

This traversal pattern (left → root → right) guarantees that values are collected in ascending order due to the BST property. We store these values in the nums array.

Phase 2: Binary Search for Each Query

For each query value x, we need to find:

1. The floor: largest value ≤ x
2. The ceiling: smallest value ≥ x

The implementation uses Python's bisect_left function strategically:

i = bisect_left(nums, x + 1) - 1  # Index for floor
j = bisect_left(nums, x)          # Index for ceiling

Here's why this works:

• bisect_left(nums, x) returns the leftmost position where x could be inserted. If x exists in the array, this gives us its index (the ceiling). If x doesn't exist, it gives us the index of the smallest value greater than x.
• bisect_left(nums, x + 1) - 1 finds where x + 1 would be inserted, then backs up one position. This gives us the largest value that is ≤ x (the floor).

Handling Edge Cases

The solution checks if the computed indices are valid:

mi = nums[i] if 0 <= i < len(nums) else -1
mx = nums[j] if 0 <= j < len(nums) else -1

• If i is out of bounds (negative), no floor exists, so we use -1
• If j is out of bounds (≥ array length), no ceiling exists, so we use -1

Time Complexity:

• DFS traversal: O(n) where n is the number of nodes
• Binary search for q queries: O(q × log n)
• Total: O(n + q × log n)

Space Complexity: O(n) for storing the sorted array of values.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given BST:

       4
      / \
     2   7
    /   / \
   1   5   8

Queries: [3, 6, 9]

Phase 1: Extract values using in-order traversal

Starting the DFS in-order traversal:

1. Go to leftmost node (1), visit left subtree (none), add 1, visit right (none)
2. Back to node 2, add 2, visit right subtree (none)
3. Back to root 4, add 4
4. Visit right subtree starting at 7
5. Visit left of 7 (node 5), add 5
6. Add 7
7. Visit right of 7 (node 8), add 8

Result: nums = [1, 2, 4, 5, 7, 8] (sorted array)

Phase 2: Process each query using binary search

Query 1: x = 3

• Find floor: bisect_left(nums, 4) - 1 = 2 - 1 = 1
  • nums[1] = 2 (largest value ≤ 3)
• Find ceiling: bisect_left(nums, 3) = 2
  • nums[2] = 4 (smallest value ≥ 3)
• Result: [2, 4]

Query 2: x = 6

• Find floor: bisect_left(nums, 7) - 1 = 4 - 1 = 3
  • nums[3] = 5 (largest value ≤ 6)
• Find ceiling: bisect_left(nums, 6) = 4
  • nums[4] = 7 (smallest value ≥ 6)
• Result: [5, 7]

Query 3: x = 9

• Find floor: bisect_left(nums, 10) - 1 = 6 - 1 = 5
  • nums[5] = 8 (largest value ≤ 9)
• Find ceiling: bisect_left(nums, 9) = 6
  • Index 6 is out of bounds (array length is 6), so ceiling = -1
• Result: [8, -1]

Final Answer: [[2, 4], [5, 7], [8, -1]]

This example demonstrates how the solution efficiently converts the tree problem into an array binary search problem, handling both standard cases and edge cases where no ceiling exists.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m × log n)

The time complexity consists of two main parts:

• O(n) for the DFS traversal to collect all node values from the BST, where n is the number of nodes. The DFS visits each node exactly once.
• O(m × log n) for processing all queries, where m is the number of queries. For each query:
  • bisect_left(nums, x + 1) takes O(log n) time (binary search on sorted array)
  • bisect_left(nums, x) takes O(log n) time (binary search on sorted array)
  • Array indexing and appending to result takes O(1) time

Since we perform 2 × log n operations for each of the m queries, the total query processing time is O(m × log n).

Therefore, the overall time complexity is O(n + m × log n).

Space Complexity: O(n)

The space complexity breaks down as follows:

• O(n) for the nums array that stores all node values from the BST
• O(n) for the recursion call stack in the worst case (skewed tree)
• O(m) for the ans array storing the results, but this is typically considered as output space

The dominant space usage is O(n) for storing the sorted array of node values and the recursion stack, giving us an overall space complexity of O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Binary Search Logic for Floor Values

A common mistake is using bisect_left(sorted_values, query_value) for finding the floor value and then simply subtracting 1. This fails when the query value exists in the array.

Incorrect approach:

# This fails when query_value exists in the array
floor_idx = bisect_left(sorted_values, query_value) - 1

Why it fails: If query_value = 5 and sorted_values = [1, 3, 5, 7], bisect_left(sorted_values, 5) returns 2 (index of 5). Subtracting 1 gives index 1 (value 3), but the correct floor should be 5 itself!

Correct solution:

# Use query_value + 1 to ensure we get the correct floor
floor_idx = bisect_left(sorted_values, query_value + 1) - 1

2. Not Handling Empty Trees

The code assumes the tree has at least one node. An empty tree will result in an empty sorted_values array, causing issues with binary search.

Problem scenario:

root = None
queries = [5, 10]
# sorted_values will be empty []

Solution - Add explicit check:

def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
    if root is None:
        return [[-1, -1] for _ in queries]
  
    # Rest of the code...

3. Misunderstanding bisect_left Behavior

Developers often confuse bisect_left with bisect_right. Using bisect_right for ceiling values would give incorrect results when the query value exists in the array.

Incorrect:

# Using bisect_right for ceiling - WRONG!
ceiling_idx = bisect_right(sorted_values, query_value)

Why it fails: If query_value = 5 exists in the array, bisect_right would skip over it and return the index of the next larger value, missing that 5 itself is a valid ceiling.

Correct:

# bisect_left correctly finds the ceiling
ceiling_idx = bisect_left(sorted_values, query_value)

4. Off-by-One Errors in Index Validation

A subtle pitfall is incorrectly checking index bounds, especially forgetting that valid indices range from 0 to len(sorted_values) - 1.

Common mistake:

# Forgetting to check upper bound properly
min_val = sorted_values[floor_idx] if floor_idx >= 0 else -1  # Missing upper bound check!

Correct validation:

min_val = sorted_values[floor_idx] if 0 <= floor_idx < len(sorted_values) else -1

5. Inefficient Query Processing Without Sorted Array

Some might attempt to search the BST directly for each query without first extracting values, leading to O(q × h) complexity where h is tree height, which could be O(q × n) for unbalanced trees.

Inefficient approach:

def find_floor_ceiling(node, query):
    # Searching BST for each query individually
    # This is O(h) per query, potentially O(n) for unbalanced trees

Better approach (as in the solution):

• Extract all values once: O(n)
• Use binary search for queries: O(q × log n)
• Total: O(n + q × log n) - much better for multiple queries