Complete binary tree inserter

Tree Breadth-First Search Design Binary Tree

65.0% acceptance

Feb 27, 2026

1154

120

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. Design an algorithm to insert a new node to a complete binary tree keeping it complete after the insertion. Implement the CBTInserter class: CBTInserter(TreeNode root) Initializes the data structure with the root of the complete binary tree. int insert(int v) Inserts a TreeNode into the tree with value Node.val == val so that the tree remains complete, and returns the value of the parent of the inserted TreeNode. TreeNode get_root() Returns the root node of the tree.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

* impl CBTInserter {

 *     fn new(root: Option<Rc<RefCell<TreeNode>>>) -> Self {

 *     }

 *     fn insert(&self, val: i32) -> i32 {

 *     }

 *     fn get_root(&self) -> Option<Rc<RefCell<TreeNode>>> {

 *     }
 * }
 */

/**
 * Your CBTInserter object will be instantiated and called as such:
 * let obj = CBTInserter::new(root);
 * let ret_1: i32 = obj.insert(val);
 * let ret_2: Option<Rc<RefCell<TreeNode>>> = obj.get_root();
 */

pub struct CBTInserter {
  root: Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>,
  tree: Vec<std::rc::Rc<std::cell::RefCell<TreeNode>>>,
}
use std::rc::Rc;
use std::cell::RefCell;
impl CBTInserter {
  pub fn new(root: Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>) -> Self {
    let mut tree = Vec::new();
    let mut queue = std::collections::VecDeque::new();
    if let Some(r) = root.clone() { queue.push_back(r); }
    while let Some(node) = queue.pop_front() {
      let left = node.borrow().left.clone();
      let right = node.borrow().right.clone();
      if let Some(l) = left { queue.push_back(l); }
      if let Some(r) = right { queue.push_back(r); }
      tree.push(node);
    }
    CBTInserter { root, tree }
  }
  pub fn insert(&mut self, val: i32) -> i32 {
    let new_node = std::rc::Rc::new(std::cell::RefCell::new(TreeNode::new(val)));
    self.tree.push(new_node.clone());
    let n = self.tree.len();
    let parent = &self.tree[(n - 2) / 2];
    let parent_val = parent.borrow().val;
    if (n - 1) % 2 == 1 { parent.borrow_mut().left = Some(new_node); }
    else { parent.borrow_mut().right = Some(new_node); }
    parent_val
  }
  pub fn get_root(&self) -> Option<std::rc::Rc<std::cell::RefCell<TreeNode>>> { self.root.clone() }
}