Delete nodes and return forest

Array Hash Table Tree Depth-First Search Binary Tree

72.5% acceptance

Feb 27, 2026

4791

145

Given the root of a binary tree, each node in the tree has a distinct value. After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees). Return the roots of the trees in the remaining forest. You may return the result in any order.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashSet;

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn del_nodes(
    root: Option<Rc<RefCell<TreeNode>>>,
    to_delete: Vec<i32>,
  ) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
    let delete_set: HashSet<i32> = to_delete.into_iter().collect();
    let mut result = Vec::new();
    Self::dfs(root, true, &delete_set, &mut result);
    result
  }

  fn dfs(
    node: Option<Rc<RefCell<TreeNode>>>,
    is_root: bool,
    delete_set: &HashSet<i32>,
    result: &mut Vec<Option<Rc<RefCell<TreeNode>>>>,
  ) -> Option<Rc<RefCell<TreeNode>>> {
    if let Some(n) = node {
      let val = n.borrow().val;
      let deleted = delete_set.contains(&val);
      if is_root && !deleted {
        result.push(Some(n.clone()));
      }
      let left = n.borrow().left.clone();
      let right = n.borrow().right.clone();
      n.borrow_mut().left = Self::dfs(left, deleted, delete_set, result);
      n.borrow_mut().right = Self::dfs(right, deleted, delete_set, result);
      if deleted { None } else { Some(n) }
    } else {
      None
    }
  }
}