#1080

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Insufficient Nodes in Root to Leaf Paths

Remove nodes in a binary tree whose all root-to-leaf paths sum to less than a given limit using DFS traversal and state tracking.

tree depth first search binary tree

Problem Statement

Given the root of a binary tree and an integer limit, remove all nodes where every root-to-leaf path passing through them has a total sum strictly less than limit. A leaf is defined as a node with no children, and pruning must occur simultaneously without revisiting already deleted nodes.

Return the root of the modified tree after deleting all insufficient nodes. The solution requires efficiently tracking the sum along each path from the root to leaves and deciding recursively whether each node should remain, highlighting the importance of state propagation in tree DFS traversal.

Examples

Example 1

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 details omitted.

Example 2

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 details omitted.

Example 3

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

Output: [1,null,-3,4]

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 5000].
-105 <= Node.val <= 105
-109 <= limit <= 109

Solution Approach

Depth-First Search with Path Sum Tracking

Perform a DFS traversal while maintaining the current sum from the root to each node. At each leaf, compare the total path sum with the limit. Return a flag indicating whether the node is insufficient so parent nodes can remove it if all child paths are insufficient.

Recursive Pruning of Insufficient Nodes

Use recursion to prune nodes: for each non-leaf node, recursively check left and right children. If both children are insufficient after recursion, mark the current node as insufficient. This ensures all paths are considered and deletion propagates correctly.

Edge Cases and Base Conditions

Handle nodes with null children carefully to avoid incorrect pruning. Check if the current node is a leaf before comparing sums. Also, handle negative limits or negative node values correctly to ensure proper path sum evaluation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) as each node is visited once during DFS. Space complexity is O(h), where h is the height of the tree, due to recursive call stack usage.

What Interviewers Usually Probe

Ask about how the path sum is tracked efficiently during traversal.
Probe if deletion propagation from leaves to root is handled correctly.
Watch for handling negative node values or limits and null children.

Common Pitfalls or Variants

Common pitfalls

Forgetting to propagate node deletion upwards when all children are insufficient.
Incorrectly computing path sums at non-leaf nodes instead of full root-to-leaf paths.
Ignoring edge cases like negative node values or limits, leading to wrong pruning.

Follow-up variants

Prune nodes where the maximum root-to-leaf path sum is below limit instead of every path.
Return the count of nodes deleted rather than the pruned tree.
Modify the tree in place without creating new nodes to save memory.

FAQ

What is the main pattern used in Insufficient Nodes in Root to Leaf Paths?

The core pattern is binary-tree traversal with state tracking, using DFS to propagate path sums and prune insufficient nodes.

How do I handle negative node values or negative limits?

Ensure that cumulative path sums correctly include negative values and compare them to the limit at leaf nodes to decide pruning.

Can this problem be solved iteratively instead of recursively?

Yes, using an explicit stack to simulate DFS and maintaining path sums, but recursion naturally handles backtracking for pruning decisions.

Do I need to revisit nodes after pruning children?

No, the recursive DFS approach allows pruning decisions to propagate upward without revisiting nodes explicitly.

What should I watch out for when a node has only one child?

Check that pruning logic considers null children correctly; a single child may cause the parent to become insufficient if the only path sum is below the limit.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# Definition for a binary tree node.
# 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: Optional[TreeNode], limit: int
    ) -> Optional[TreeNode]:
        if root is None:
            return None
        limit -= root.val
        if root.left is None and root.right is None:
            return None if limit > 0 else root
        root.left = self.sufficientSubset(root.left, limit)
        root.right = self.sufficientSubset(root.right, limit)
        return None if root.left is None and root.right is None else root

Continue Practicing

#1110 delete nodes and return forest #1038 binary search tree to greater sum tree #1123 lowest common ancestor of deepest leaves