LeetCode 2476 - Closest Nodes Queries in a Binary Search Tree

LeetCode Problem 2476

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Tree, Depth-First Search, Binary Search Tree, Binary Tree

Solution

Problem Understanding

The problem gives us the root of a binary search tree, abbreviated as BST, along with a list of query values. For every query, we must determine two numbers:

• The largest value in the BST that is less than or equal to the query.
• The smallest value in the BST that is greater than or equal to the query.

If either value does not exist, we return -1 for that position.

The final result is a 2D array where each query produces one pair [mini, maxi].

A binary search tree has a very important property:

• Every value in the left subtree is smaller than the current node.
• Every value in the right subtree is larger than the current node.

Because of this ordering property, the values of a BST become sorted if we perform an inorder traversal.

For example, consider this BST:

        6
      /   \
     2     13
    / \    / \
   1   4  9  15
             /
            14

Its inorder traversal is:

[1, 2, 4, 6, 9, 13, 14, 15]

Now suppose the query is 5.

• The largest value less than or equal to 5 is 4.
• The smallest value greater than or equal to 5 is 6.

So the answer is [4, 6].

The constraints are large:

• Up to 10^5 tree nodes.
• Up to 10^5 queries.

These limits immediately tell us that a naive solution that scans the entire tree for every query will be too slow. A quadratic style approach could reach 10^10 operations, which is far beyond acceptable limits.

Important edge cases include:

• Queries smaller than every node in the tree.
• Queries larger than every node in the tree.
• Queries exactly equal to a node value.
• Very skewed trees that behave like linked lists.
• Large numbers of queries.

The problem guarantees the input tree is a valid BST, which is the key property that enables efficient searching.

Approaches

Brute Force Approach

The most straightforward approach is to process every query independently by traversing the entire tree.

For each query:

1. Visit every node in the BST.
2. Track the largest value less than or equal to the query.
3. Track the smallest value greater than or equal to the query.

This works because eventually we inspect every node, so we cannot miss a valid candidate.

However, the complexity is extremely poor.

If the tree contains m nodes and there are n queries:

• Each query requires O(m) work.
• Total complexity becomes O(m * n).

With both values potentially equal to 10^5, this can become 10^10 operations.

This approach is correct but far too slow.

Optimal Approach

The key observation is that a BST produces sorted values through inorder traversal.

Once we convert the BST into a sorted array, the problem becomes:

For each query, find:

• The rightmost value less than or equal to the query.
• The leftmost value greater than or equal to the query.

This is exactly what binary search is designed for.

The optimized process is:

1. Perform inorder traversal to create a sorted array.
2. Use binary search for every query.

Because binary search runs in logarithmic time, each query becomes efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * n)	O(h)	Traverse the whole tree for every query
Optimal	O(m + n log m)	O(m)	Inorder traversal plus binary search

Here:

• m = number of tree nodes
• n = number of queries
• h = tree height

Algorithm Walkthrough

Step 1: Perform inorder traversal

Traverse the BST using inorder traversal:

1. Visit left subtree.
2. Visit current node.
3. Visit right subtree.

Because the tree is a BST, inorder traversal naturally produces values in sorted order.

For the example tree:

        6
      /   \
     2     13
    / \    / \
   1   4  9  15
             /
            14

The traversal becomes:

[1, 2, 4, 6, 9, 13, 14, 15]

We store this array because binary search requires sorted input.

Step 2: Process each query independently

For every query value:

• Find the insertion position where the query could be placed while keeping the array sorted.
• Use neighboring indices to determine floor and ceiling values.

We use two binary searches:

1. bisect_right

• Finds the first position strictly greater than the query.
• The element just before that position is the largest value less than or equal to the query.

2. bisect_left

• Finds the first position greater than or equal to the query.
• That element is the smallest value greater than or equal to the query.

Step 3: Compute the floor value

Suppose:

values = [1, 2, 4, 6, 9]
query = 5

bisect_right(values, 5) returns index 3.

This means:

values[2] = 4

is the last value less than or equal to 5.

So:

mini = 4

If the returned index is 0, then no smaller value exists.

Step 4: Compute the ceiling value

Using the same example:

bisect_left(values, 5)

returns index 3.

That corresponds to:

values[3] = 6

So:

maxi = 6

If the returned index equals the array length, then no larger value exists.

Step 5: Store the result

Append:

[mini, maxi]

to the answer list for every query.

Why it works

The correctness depends on two properties.

First, inorder traversal of a BST always produces a sorted sequence. This guarantees that binary search can be applied correctly.

Second, binary search precisely identifies insertion boundaries:

• bisect_right identifies the position after the final occurrence less than or equal to the query.
• bisect_left identifies the first occurrence greater than or equal to the query.

These positions directly correspond to the required floor and ceiling values, ensuring every query is answered correctly.

Python Solution

from bisect import bisect_left, bisect_right
from typing import List, Optional

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

        sorted_values = []

        def inorder(node: Optional[TreeNode]) -> None:
            if not node:
                return

            inorder(node.left)
            sorted_values.append(node.val)
            inorder(node.right)

        inorder(root)

        answer = []

        for query in queries:

            right_index = bisect_right(sorted_values, query)

            if right_index == 0:
                mini = -1
            else:
                mini = sorted_values[right_index - 1]

            left_index = bisect_left(sorted_values, query)

            if left_index == len(sorted_values):
                maxi = -1
            else:
                maxi = sorted_values[left_index]

            answer.append([mini, maxi])

        return answer

The implementation begins with an inorder traversal helper function. This recursively walks through the BST in sorted order and stores all node values inside sorted_values.

Once traversal is complete, the tree has effectively been converted into a sorted array.

For every query, the code performs two binary searches:

• bisect_right determines the floor candidate.
• bisect_left determines the ceiling candidate.

Boundary checks are necessary because binary search may return positions outside the valid range:

• If no smaller value exists, return -1.
• If no larger value exists, return -1.

Each result pair is appended to answer, which is returned at the end.

Go Solution

package main

import "sort"

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func closestNodes(root *TreeNode, queries []int) [][]int {
    values := []int{}

    var inorder func(node *TreeNode)

    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }

        inorder(node.Left)
        values = append(values, node.Val)
        inorder(node.Right)
    }

    inorder(root)

    result := make([][]int, 0, len(queries))

    for _, query := range queries {

        rightIndex := sort.Search(len(values), func(i int) bool {
            return values[i] > query
        })

        mini := -1
        if rightIndex > 0 {
            mini = values[rightIndex-1]
        }

        leftIndex := sort.Search(len(values), func(i int) bool {
            return values[i] >= query
        })

        maxi := -1
        if leftIndex < len(values) {
            maxi = values[leftIndex]
        }

        result = append(result, []int{mini, maxi})
    }

    return result
}

The Go version follows the same algorithmic structure as the Python solution.

The primary difference is that Go does not provide built in bisect_left and bisect_right helpers. Instead, we use sort.Search, which performs binary search over index ranges.

Two separate searches are used:

• One searches for the first value greater than the query.
• One searches for the first value greater than or equal to the query.

Go slices dynamically resize similarly to Python lists, so storing inorder traversal values is straightforward.

Nil checks are required for tree traversal because Go uses pointers for tree nodes.

Worked Examples

Example 1

root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14]
queries = [2,5,16]

Step 1: Inorder traversal

The BST becomes:

sorted_values = [1,2,4,6,9,13,14,15]

Query = 2

Operation	Result
bisect_right([1,2,4,6,9,13,14,15], 2)	2
mini	values[1] = 2
bisect_left([1,2,4,6,9,13,14,15], 2)	1
maxi	values[1] = 2

Answer:

[2,2]

Query = 5

Operation	Result
bisect_right(..., 5)	3
mini	values[2] = 4
bisect_left(..., 5)	3
maxi	values[3] = 6

Answer:

[4,6]

Query = 16

Operation	Result
bisect_right(..., 16)	8
mini	values[7] = 15
bisect_left(..., 16)	8
maxi	-1

Final result:

[[2,2],[4,6],[15,-1]]

Example 2

root = [4,null,9]
queries = [3]

Step 1: Inorder traversal

sorted_values = [4,9]

Query = 3

Operation	Result
bisect_right([4,9], 3)	0
mini	-1
bisect_left([4,9], 3)	0
maxi	4

Final result:

[[-1,4]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m + n log m)	Inorder traversal takes O(m), each query uses binary search
Space	O(m)	Stores all BST values in a sorted array

The inorder traversal visits every node exactly once, producing linear complexity relative to the number of tree nodes.

Each query performs two binary searches over the sorted array. Binary search takes O(log m) time, so n queries require O(n log m) total work.

The dominant extra memory usage comes from storing all BST values in the inorder array.

Test Cases

# Helper TreeNode class for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

solution = Solution()

# Example 1
root1 = TreeNode(
    6,
    TreeNode(
        2,
        TreeNode(1),
        TreeNode(4)
    ),
    TreeNode(
        13,
        TreeNode(9),
        TreeNode(
            15,
            TreeNode(14),
            None
        )
    )
)

assert solution.closestNodes(root1, [2, 5, 16]) == [
    [2, 2],
    [4, 6],
    [15, -1]
]  # Standard mixed queries

# Example 2
root2 = TreeNode(4, None, TreeNode(9))

assert solution.closestNodes(root2, [3]) == [
    [-1, 4]
]  # Query smaller than minimum node

# Exact matches
root3 = TreeNode(5, TreeNode(3), TreeNode(8))

assert solution.closestNodes(root3, [5, 3, 8]) == [
    [5, 5],
    [3, 3],
    [8, 8]
]  # Queries exactly equal to nodes

# Query larger than every node
assert solution.closestNodes(root3, [10]) == [
    [8, -1]
]  # No ceiling exists

# Query smaller than every node
assert solution.closestNodes(root3, [1]) == [
    [-1, 3]
]  # No floor exists

# Single chain BST
root4 = TreeNode(
    1,
    None,
    TreeNode(
        2,
        None,
        TreeNode(
            3,
            None,
            TreeNode(4)
        )
    )
)

assert solution.closestNodes(root4, [2, 5]) == [
    [2, 2],
    [4, -1]
]  # Skewed tree structure

# Multiple mixed queries
assert solution.closestNodes(root3, [4, 6, 7]) == [
    [3, 5],
    [5, 8],
    [5, 8]
]  # Values between existing nodes

# Minimum size tree
root5 = TreeNode(1, None, TreeNode(2))

assert solution.closestNodes(root5, [1, 2, 0, 3]) == [
    [1, 1],
    [2, 2],
    [-1, 1],
    [2, -1]
]  # Smallest allowed BST

Test	Why
Standard mixed queries	Verifies normal floor and ceiling behavior
Query smaller than minimum	Ensures missing floor returns -1
Exact matches	Ensures equality is handled correctly
Query larger than maximum	Ensures missing ceiling returns -1
Skewed tree	Validates traversal on unbalanced BSTs
Between-node values	Tests binary search boundaries
Minimum size tree	Verifies smallest valid input

Edge Cases

Query smaller than every node

Suppose the BST values are:

[4, 7, 10]

and the query is:

2

No value in the tree is less than or equal to 2.

This can easily produce index underflow bugs if we blindly access index - 1 after binary search. The implementation prevents this by checking whether the insertion position is 0. If so, it returns -1 for the floor value.

Query larger than every node

Suppose the BST values are:

[4, 7, 10]

and the query is:

20

No value is greater than or equal to 20.

Binary search returns an insertion index equal to the array length. Attempting to access that index would cause an out of bounds error. The implementation explicitly checks for this condition and returns -1 for the ceiling value.

Query exactly equal to a node value

If the query already exists in the BST, both answers should equal the query itself.

For example:

values = [1, 3, 5, 7]
query = 5

A common bug is accidentally returning neighboring values instead of the exact match. Using bisect_left and bisect_right correctly guarantees that exact matches are handled properly.

Highly unbalanced BST

A BST may become completely skewed, behaving like a linked list.

Example:

1
 \
  2
   \
    3
     \
      4

A naive recursive search per query could become inefficient if repeated many times. Our approach performs only one traversal of the tree, then relies on efficient binary searches afterward, making query processing fast regardless of tree shape.