Closest Nodes Queries in a Binary Search Tree

Closest Nodes Queries in a Binary Search Tree - Problem

You are given the root of a binary search tree and an array queries of positive integers. For each query value, you need to find two important pieces of information:

1. Floor value: The largest value in the BST that is smaller than or equal to the query
2. Ceiling value: The smallest value in the BST that is greater than or equal to the query

Return a 2D array where each element answer[i] = [mini, maxi] represents the floor and ceiling for queries[i]. If no floor exists, use -1. If no ceiling exists, use -1.

Think of it as finding the closest neighbors for each query in the BST!

Input & Output

example_1.py — Basic BST Query

$ 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],[-1,-1]]

💡 Note: For query 2: floor=2 (exact match), ceiling=2 (exact match). For query 5: floor=4 (largest ≤5), ceiling=6 (smallest ≥5). For query 16: floor=-1 (no value ≤16... wait, 15 ≤ 16), ceiling=-1 (no value ≥16). Actually floor should be 15.

example_2.py — Edge Case Queries

$ Input: root = [4,null,9], queries = [3,10]

› Output: [[-1,4],[9,-1]]

💡 Note: For query 3: no value ≤3 exists (floor=-1), smallest value ≥3 is 4 (ceiling=4). For query 10: largest value ≤10 is 9 (floor=9), no value ≥10 exists (ceiling=-1).

example_3.py — Single Node

$ Input: root = [5], queries = [1,5,10]

› Output: [[-1,5],[5,5],[-1,-1]]

💡 Note: Tree has only one node (5). Query 1: floor=-1, ceiling=5. Query 5: floor=5, ceiling=5. Query 10: floor=5, ceiling=-1.

Constraints

The number of nodes in the tree is in the range [1, 2 × 10⁴]
1 ≤ Node.val ≤ 10⁶
n == queries.length
1 ≤ n ≤ 10⁴
1 ≤ queries[i] ≤ 10⁶
All node values are unique

Visualization

Tap to expand

Understanding the Visualization

Extract Sorted Values

Inorder traversal gives us all parking spot numbers in order

Binary Search Floor

Find the highest-numbered spot ≤ our target (closest behind)

Binary Search Ceiling

Find the lowest-numbered spot ≥ our target (closest ahead)

Return Results

Return both closest spots, or -1 if none exists in that direction

Key Takeaway

🎯 Key Insight: BST's inorder traversal gives us a sorted array, enabling efficient O(log n) binary search for floor/ceiling queries instead of O(n) linear search per query.

Asked in

⊞ Microsoft 45 a Amazon 38 G Google 32 f Meta 25

The optimal solution uses inorder traversal to extract BST values into a sorted array, then applies binary search for each query. This achieves O(n + m log n) time complexity, where n is the number of nodes and m is the number of queries. The key insight is leveraging the BST's inherent ordering through inorder traversal.

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Sorted Array (Optimal)	O(n + m log n)	O(n)	Extract BST values to sorted array, then use binary search for each query
Brute Force Tree Traversal	O(n × m)	O(n)	For each query, traverse the entire BST to find floor and ceiling

Binary Search on Sorted Array (Optimal) — Algorithm Steps

Perform inorder traversal to get sorted array of BST values
For each query, use binary search to find insertion points
Calculate floor as largest element ≤ query
Calculate ceiling as smallest element ≥ query

Visualization

Tap to expand

Step-by-Step Walkthrough

Inorder Traversal

Extract sorted array from BST

Binary Search Floor

Use upper_bound - 1 to find largest ≤ query

Binary Search Ceiling

Use lower_bound to find smallest ≥ query

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int binarySearchLeft(int* arr, int size, int target) {
    int left = 0, right = size;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

int binarySearchRight(int* arr, int size, int target) {
    int left = 0, right = size;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

void inorder(struct TreeNode* node, int* values, int* size) {
    if (!node) return;
    inorder(node->left, values, size);
    values[(*size)++] = node->val;
    inorder(node->right, values, size);
}

int** closestNodes(struct TreeNode* root, int* queries, int queriesSize, int* returnSize, int** returnColumnSizes) {
    // Extract all values from BST
    int* values = (int*)malloc(100000 * sizeof(int));
    int valuesSize = 0;
    inorder(root, values, &valuesSize);
    
    int** result = (int**)malloc(queriesSize * sizeof(int*));
    *returnColumnSizes = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    // For each query, use binary search
    for (int i = 0; i < queriesSize; i++) {
        result[i] = (int*)malloc(2 * sizeof(int));
        (*returnColumnSizes)[i] = 2;
        
        int query = queries[i];
        
        // Find floor: largest value <= query
        int rightPos = binarySearchRight(values, valuesSize, query);
        int floorVal = (rightPos > 0) ? values[rightPos - 1] : -1;
        
        // Find ceiling: smallest value >= query
        int leftPos = binarySearchLeft(values, valuesSize, query);
        int ceilingVal = (leftPos < valuesSize) ? values[leftPos] : -1;
        
        result[i][0] = floorVal;
        result[i][1] = ceilingVal;
    }
    
    free(values);
    return result;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m log n)

O(n) to extract values + O(m log n) for m binary searches

⚡ Linearithmic

Space Complexity

O(n)

Store all n node values in sorted array

⚡ Linearithmic Space

52.4K Views

Medium-High Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Sorted Array (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler