Maximum width of binary tree

Tree Depth-First Search Breadth-First Search Binary Tree

45.3% acceptance

Feb 20, 2026

9671

1317

Given the root of a binary tree, return the maximum width of the given tree. The maximum width of a tree is the maximum width among all levels. Width of a level is the length between the leftmost and rightmost non-null nodes, including null nodes between them.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
  pub fn width_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    let mut max_width = 0u64;
    let mut queue: VecDeque<(Rc<RefCell<TreeNode>>, u64)> = VecDeque::new();
    if let Some(r) = root {
      queue.push_back((r, 0));
    }
    while !queue.is_empty() {
      let level_size = queue.len();
      let (_, first_idx) = queue.front().unwrap().clone();
      let mut last_idx = first_idx;
      for _ in 0..level_size {
        let (node, idx) = queue.pop_front().unwrap();
        last_idx = idx;
        let b = node.borrow();
        let norm = idx - first_idx;
        if let Some(l) = b.left.clone() {
          queue.push_back((l, norm * 2));
        }
        if let Some(r) = b.right.clone() {
          queue.push_back((r, norm * 2 + 1));
        }
      }
      max_width = max_width.max(last_idx - first_idx + 1);
    }
    max_width as i32
  }
}