Insufficient nodes in root to leaf paths

Tree Depth-First Search Binary Tree

54.9% acceptance

Feb 27, 2026

751

739

Given the root of a binary tree and an integer limit, delete all insufficient nodes in the tree simultaneously, and return the root of the resulting binary tree. A node is insufficient if every root to leaf path intersecting this node has a sum strictly less than limit. A leaf is a node with no children.

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 sufficient_subset(root: Option<Rc<RefCell<TreeNode>>>, limit: i32) -> Option<Rc<RefCell<TreeNode>>> {
    match root {
      None => None,
      Some(node) => {
        let val = node.borrow().val;
        let is_leaf = node.borrow().left.is_none() && node.borrow().right.is_none();
        if is_leaf {
          return if val >= limit { Some(node) } else { None };
        }
        let left = node.borrow().left.clone();
        let right = node.borrow().right.clone();
        node.borrow_mut().left = Self::sufficient_subset(left, limit - val);
        node.borrow_mut().right = Self::sufficient_subset(right, limit - val);
        if node.borrow().left.is_none() && node.borrow().right.is_none() {
          None
        } else {
          Some(node)
        }
      }
    }
  }
}