Closest nodes queries in a binary search tree

Array Binary Search Tree Depth-First Search Binary Search Tree Binary Tree

44.1% acceptance

Feb 27, 2026

535

142

You are given the root of a binary search tree and an array queries of size n consisting of positive integers. Find a 2D array answer of size n where answer[i] = [mini, maxi]: mini is the largest value in the tree that is smaller than or equal to queries[i]. (-1 if none) maxi is the smallest value in the tree that is greater than or equal to queries[i]. (-1 if none) Return the array answer.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn closest_nodes(root: Option<Rc<RefCell<TreeNode>>>, queries: Vec<i32>) -> Vec<Vec<i32>> {
    // Inorder traversal gives sorted array; binary search per query
    let mut vals: Vec<i32> = Vec::new();
    fn inorder(node: &Option<Rc<RefCell<TreeNode>>>, vals: &mut Vec<i32>) {
      if let Some(n) = node {
        let b = n.borrow();
        inorder(&b.left, vals);
        vals.push(b.val);
        inorder(&b.right, vals);
      }
    }
    inorder(&root, &mut vals);

    queries.iter().map(|&q| {
      let mini = match vals.partition_point(|&x| x <= q) {
        0 => -1,
        i => vals[i - 1],
      };
      let maxi = match vals.partition_point(|&x| x < q) {
        i if i < vals.len() => vals[i],
        _ => -1,
      };
      vec![mini, maxi]
    }).collect()
  }
}