Problem

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.

Examples

Example 1

1
2
3
4
5


![](https://assets.leetcode.com/uploads/2019/06/05/insufficient-11.png)

Input: root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1
Output: [1,2,3,4,null,null,7,8,9,null,14]

Example 2

1
2
3
4
5


![](https://assets.leetcode.com/uploads/2019/06/05/insufficient-3.png)

Input: root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22
Output: [5,4,8,11,null,17,4,7,null,null,null,5]

Example 3

1
2
3
4
5
6


![](https://assets.leetcode.com/uploads/2019/06/11/screen-
shot-2019-06-11-at-83301-pm.png)

Input: root = [1,2,-3,-5,null,4,null], limit = -1
Output: [1,null,-3,4]

Constraints

  • The number of nodes in the tree is in the range [1, 5000].
  • -10^5 <= Node.val <= 10^5
  • -109 <= limit <= 10^9

Solution

Method 1 – Postorder DFS Pruning

Intuition

We want to remove nodes where every root-to-leaf path through that node has a sum less than the limit. By using postorder DFS, we can check the sum for each subtree and prune insufficient nodes from the bottom up.

Approach

  1. Use a recursive DFS function that returns the pruned subtree.
  2. For each node:
    • If it is a leaf, check if the path sum including this node is at least the limit. If not, return null.
    • Recursively prune left and right children, passing the updated sum.
    • If both children are pruned (null), and the node is not sufficient, prune this node as well.
  3. Return the pruned tree.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
        return dfs(root, 0, limit);
    }
private:
    TreeNode* dfs(TreeNode* node, int sum, int limit) {
        if (!node) return nullptr;
        sum += node->val;
        if (!node->left && !node->right)
            return sum >= limit ? node : nullptr;
        node->left = dfs(node->left, sum, limit);
        node->right = dfs(node->right, sum, limit);
        if (!node->left && !node->right) return nullptr;
        return node;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}
func sufficientSubset(root *TreeNode, limit int) *TreeNode {
    var dfs func(*TreeNode, int) *TreeNode
    dfs = func(node *TreeNode, sum int) *TreeNode {
        if node == nil {
            return nil
        }
        sum += node.Val
        if node.Left == nil && node.Right == nil {
            if sum >= limit {
                return node
            }
            return nil
        }
        node.Left = dfs(node.Left, sum)
        node.Right = dfs(node.Right, sum)
        if node.Left == nil && node.Right == nil {
            return nil
        }
        return node
    }
    return dfs(root, 0)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
class Solution {
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        return dfs(root, 0, limit);
    }
    private TreeNode dfs(TreeNode node, int sum, int limit) {
        if (node == null) return null;
        sum += node.val;
        if (node.left == null && node.right == null)
            return sum >= limit ? node : null;
        node.left = dfs(node.left, sum, limit);
        node.right = dfs(node.right, sum, limit);
        if (node.left == null && node.right == null) return null;
        return node;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

data class TreeNode(var `val`: Int, var left: TreeNode? = null, var right: TreeNode? = null)
class Solution {
    fun sufficientSubset(root: TreeNode?, limit: Int): TreeNode? {
        fun dfs(node: TreeNode?, sum: Int): TreeNode? {
            if (node == null) return null
            val s = sum + node.`val`
            if (node.left == null && node.right == null)
                return if (s >= limit) node else null
            node.left = dfs(node.left, s)
            node.right = dfs(node.right, s)
            return if (node.left == null && node.right == null) null else node
        }
        return dfs(root, 0)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
        def dfs(node: TreeNode, s: int) -> TreeNode:
            if not node:
                return None
            s += node.val
            if not node.left and not node.right:
                return node if s >= limit else None
            node.left = dfs(node.left, s)
            node.right = dfs(node.right, s)
            if not node.left and not node.right:
                return None
            return node
        return dfs(root, 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

use std::rc::Rc;
use std::cell::RefCell;
#[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 }
    }
}
pub struct Solution;
impl Solution {
    pub fn sufficient_subset(root: Option<Rc<RefCell<TreeNode>>>, limit: i32) -> Option<Rc<RefCell<TreeNode>>> {
        fn dfs(node: Option<Rc<RefCell<TreeNode>>>, sum: i32, limit: i32) -> Option<Rc<RefCell<TreeNode>>> {
            if let Some(n) = node {
                let mut n = n.borrow_mut();
                let s = sum + n.val;
                if n.left.is_none() && n.right.is_none() {
                    return if s >= limit { Some(Rc::new(RefCell::new(TreeNode::new(n.val)))) } else { None };
                }
                n.left = dfs(n.left.take(), s, limit);
                n.right = dfs(n.right.take(), s, limit);
                if n.left.is_none() && n.right.is_none() {
                    return None;
                }
                return Some(Rc::new(RefCell::new(TreeNode {
                    val: n.val,
                    left: n.left.clone(),
                    right: n.right.clone(),
                })));
            }
            None
        }
        dfs(root, 0, limit)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val ?? 0;
    this.left = left ?? null;
    this.right = right ?? null;
  }
}
class Solution {
  sufficientSubset(root: TreeNode | null, limit: number): TreeNode | null {
    function dfs(node: TreeNode | null, s: number): TreeNode | null {
      if (!node) return null;
      s += node.val;
      if (!node.left && !node.right) return s >= limit ? node : null;
      node.left = dfs(node.left, s);
      node.right = dfs(node.right, s);
      if (!node.left && !node.right) return null;
      return node;
    }
    return dfs(root, 0);
  }
}

Complexity

  • ⏰ Time complexity: O(n) — Each node is visited once.
  • 🧺 Space complexity: O(h) — Call stack for recursion, where h is the height of the tree.