Add one row to tree

Tree Depth-First Search Breadth-First Search Binary Tree

64.1% acceptance

Feb 20, 2026

3670

271

Given the root of a binary tree and two integers val and depth, add a row of nodes with value val at the given depth.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn add_one_row(
    root: Option<Rc<RefCell<TreeNode>>>,
    val: i32,
    depth: i32,
  ) -> Option<Rc<RefCell<TreeNode>>> {
    if depth == 1 {
      let new_root = Rc::new(RefCell::new(TreeNode::new(val)));
      new_root.borrow_mut().left = root;
      return Some(new_root);
    }
    let root_ref = root.clone();
    let mut queue = std::collections::VecDeque::new();
    if let Some(r) = root_ref {
      queue.push_back((r, 1));
    }
    while let Some((node, d)) = queue.pop_front() {
      if d == depth - 1 {
        let old_left = node.borrow().left.clone();
        let old_right = node.borrow().right.clone();
        let new_left = Rc::new(RefCell::new(TreeNode::new(val)));
        new_left.borrow_mut().left = old_left;
        let new_right = Rc::new(RefCell::new(TreeNode::new(val)));
        new_right.borrow_mut().right = old_right;
        node.borrow_mut().left = Some(new_left);
        node.borrow_mut().right = Some(new_right);
      } else {
        let left = node.borrow().left.clone();
        let right = node.borrow().right.clone();
        if let Some(l) = left { queue.push_back((l, d + 1)); }
        if let Some(r) = right { queue.push_back((r, d + 1)); }
      }
    }
    root
  }
}