Check completeness of a binary tree

Tree Breadth-First Search Binary Tree

59.0% acceptance

Feb 27, 2026

4530

Given the root of a binary tree, determine if it is a complete binary tree. In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

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 is_complete_tree(root: Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>) -> bool {
    let mut queue = std::collections::VecDeque::new();
    queue.push_back(root);
    let mut found_null = false;
    while let Some(node) = queue.pop_front() {
      match node {
        None => { found_null = true; }
        Some(n) => {
          if found_null { return false; }
          let n = n.borrow();
          queue.push_back(n.left.clone());
          queue.push_back(n.right.clone());
        }
      }
    }
    true
  }
}