Closest Nodes Queries in a Binary Search Tree

Medium
1960.

Closest Nodes Queries in a Binary Search Tree

Closest Nodes Queries in a Binary Search Tree is a medium coding problem on arrays, depth-first search and binary search, asked in Amazon interviews.

You are given the root of a binary search tree and an array queries of positive integers.

For each query q return a pair [mini, maxi] where:

  • mini is the largest value in the tree that is less than or equal to q, or -1 if there is none;
  • maxi is the smallest value in the tree that is greater than or equal to q, or -1 if there is none.

Return the pairs in the order of the queries.

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
2 is in the tree, so both answers are 2. For 5 the closest values around it are 4 and 6. Nothing is at least 16, so its upper answer is -1.

Example 2

Input
root = [4,null,9], queries = [3]
Output
[[-1,4]]
Explanation
Nothing in the tree is at most 3; the smallest value at least 3 is 4.

Example 3

Input
root = [8,3], queries = [8,1,20]
Output
[[8,8],[-1,3],[8,-1]]
Explanation
8 is in the tree, so it answers both sides. Nothing is at most 1 (the smallest value at least 1 is 3), and nothing is at least 20.

Constraints

  • 2 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^6
  • root is a valid binary search tree with distinct values
  • 1 <= queries.length <= 10^5
  • 1 <= queries[i] <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number[]} queries
 * @return {number[][]}
 */
var closestNodes = function(root, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Closest Nodes Queries in a Binary Search Tree — Solution

Closest Nodes Queries in a Binary Search Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Closest Nodes Queries in a Binary Search Tree is a medium coding problem on arrays, depth-first search and binary search, asked in Amazon interviews.

Problem statement

You are given the root of a binary search tree and an array queries of positive integers.

For each query q return a pair [mini, maxi] where:

  • mini is the largest value in the tree that is less than or equal to q, or -1 if there is none;
  • maxi is the smallest value in the tree that is greater than or equal to q, or -1 if there is none.

Return the pairs in the order of the queries.

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: 2 is in the tree, so both answers are 2. For 5 the closest values around it are 4 and 6. Nothing is at least 16, so its upper answer is -1.

Example 2

Input: root = [4,null,9], queries = [3]
Output: [[-1,4]]
Explanation: Nothing in the tree is at most 3; the smallest value at least 3 is 4.

Example 3

Input: root = [8,3], queries = [8,1,20]
Output: [[8,8],[-1,3],[8,-1]]
Explanation: 8 is in the tree, so it answers both sides. Nothing is at most 1 (the smallest value at least 1 is 3), and nothing is at least 20.

Constraints

  • 2 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^6
  • root is a valid binary search tree with distinct values
  • 1 <= queries.length <= 10^5
  • 1 <= queries[i] <= 10^6

Hints for Closest Nodes Queries in a Binary Search Tree

  1. Hint 1

    The tree can be badly unbalanced — a chain of 10^5 nodes — so walking it from the root once per query can be too slow.

  2. Hint 2

    An in-order traversal of a BST lists its values in increasing order. Do that once.

  3. Hint 3

    With the sorted list, each query is a binary search: the first value >= q gives maxi, and the value just before it (or the found value itself when it equals q) gives mini.

How to solve Closest Nodes Queries in a Binary Search Tree

Flatten the BST into its sorted in-order sequence once, then answer every query with one binary search for the first value not below it.

Approach

  1. Traverse the tree in order to collect its values in increasing order into vals.
  2. For a query q, find i, the first index with vals[i] >= q (lower bound).
  3. maxi is vals[i] if i < len(vals), else -1.
  4. mini is q when vals[i] == q; otherwise vals[i - 1] if i > 0, else -1.

Why it works

vals is sorted, so every value before position i is below q and every value from i on is at least q. The smallest value at least q is therefore vals[i], and the largest value at most q is vals[i] itself when it equals q, or else the last value before it.

Complexity

  • Time — O(n + m log n) for n nodes and m queries
  • Space — O(n) for the sorted values

Pitfalls

  • Searching from the root per query costs O(height), which is O(n) on a skewed tree — 10^10 steps in the worst case.
  • A query equal to a tree value answers [q, q]; do not take the strictly smaller neighbour.

Reference solution

Python

from bisect import bisect_left
from typing import List, Optional

def closestNodes(root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
    vals = []
    stack = []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        vals.append(node.val)
        node = node.right
    out = []
    for q in queries:
        i = bisect_left(vals, q)
        hi = vals[i] if i < len(vals) else -1
        if i < len(vals) and vals[i] == q:
            lo = q
        else:
            lo = vals[i - 1] if i > 0 else -1
        out.append([lo, hi])
    return out

Java

public static int[][] closestNodes(TreeNode root, int[] queries) {
    List<Integer> list = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    while (!stack.isEmpty() || node != null) {
        while (node != null) { stack.push(node); node = node.left; }
        node = stack.pop();
        list.add(node.val);
        node = node.right;
    }
    int n = list.size();
    int[] vals = new int[n];
    for (int i = 0; i < n; i++) vals[i] = list.get(i);
    int[][] out = new int[queries.length][];
    for (int k = 0; k < queries.length; k++) {
        int q = queries[k], lo = 0, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (vals[mid] < q) lo = mid + 1; else hi = mid;
        }
        int maxi = lo < n ? vals[lo] : -1;
        int mini = lo < n && vals[lo] == q ? q : (lo > 0 ? vals[lo - 1] : -1);
        out[k] = new int[] { mini, maxi };
    }
    return out;
}

C++

vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
    vector<int> vals;
    vector<TreeNode*> stack;
    TreeNode* node = root;
    while (!stack.empty() || node) {
        while (node) { stack.push_back(node); node = node->left; }
        node = stack.back();
        stack.pop_back();
        vals.push_back(node->val);
        node = node->right;
    }
    vector<vector<int>> out;
    for (int q : queries) {
        int i = (int) (lower_bound(vals.begin(), vals.end(), q) - vals.begin());
        int n = (int) vals.size();
        int maxi = i < n ? vals[i] : -1;
        int mini = i < n && vals[i] == q ? q : (i > 0 ? vals[i - 1] : -1);
        out.push_back({mini, maxi});
    }
    return out;
}

JavaScript

var closestNodes = function(root, queries) {
    var vals = [], stack = [], node = root;
    while (stack.length > 0 || node !== null) {
        while (node !== null) { stack.push(node); node = node.left; }
        node = stack.pop();
        vals.push(node.val);
        node = node.right;
    }
    var out = [];
    for (var k = 0; k < queries.length; k++) {
        var q = queries[k], lo = 0, hi = vals.length;
        while (lo < hi) {
            var mid = (lo + hi) >> 1;
            if (vals[mid] < q) lo = mid + 1; else hi = mid;
        }
        var maxi = lo < vals.length ? vals[lo] : -1;
        var mini = lo < vals.length && vals[lo] === q ? q : (lo > 0 ? vals[lo - 1] : -1);
        out.push([mini, maxi]);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Depth-First Search (DFS)