Median of a binary search tree level

Tree Depth-First Search Breadth-First Search Binary Search Tree Binary Tree

88.0% acceptance

Apr 3, 2026

You are given the root of a Binary Search Tree (BST) and an integer level. The root node is at level 0. Each level represents the distance from the root. Return the median value of all node values present at the given level. If the level does not exist or contains no nodes, return -1. The median is defined as the middle element after sorting the values at that level in non-decreasing order. If the number of values at that level is even, return the upper median (the larger of the two middle elements after sorting).

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn level_median(root: Option<Rc<RefCell<TreeNode>>>, level: i32) -> i32 {
    let Some(root) = root else {
      return -1;
    };

    let target_level = level as usize;
    let mut queue = std::collections::VecDeque::new();
    queue.push_back(root);

    for current_level in 0..=target_level {
      if queue.is_empty() {
        return -1;
      }

      let level_size = queue.len();
      if current_level == target_level {
        let mut values = Vec::with_capacity(level_size);
        for _ in 0..level_size {
          let node = queue.pop_front().unwrap();
          values.push(node.borrow().val);
        }
        let median_index = values.len() / 2;
        values.select_nth_unstable(median_index);
        return values[median_index];
      }

      for _ in 0..level_size {
        let node = queue.pop_front().unwrap();
        let node_ref = node.borrow();
        if let Some(left) = node_ref.left.clone() {
          queue.push_back(left);
        }
        if let Some(right) = node_ref.right.clone() {
          queue.push_back(right);
        }
      }
    }

    -1
  }
}