LeetCode 1080: Insufficient Nodes in Root to Leaf Paths

Problem Restatement

We are given the root of a binary tree and an integer limit.

A node is insufficient if every root-to-leaf path through that node has a sum strictly less than limit.

We need to delete all insufficient nodes and return the root of the resulting tree.

The official constraints state that the number of nodes is in [1, 5000] and -10^5 <= Node.val <= 10^5.

Input and Output

Function shape:

def sufficientSubset(root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:
    ...

Examples

Example 1:

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

Some paths sum to less than 1 and those nodes are removed.

Key Insight

Use DFS. For each node, we need to know the maximum path sum from that node to any leaf in its subtree.

A node is insufficient if the maximum path sum ending at a leaf below it (plus the current prefix from root) is still less than limit.

Equivalently: reduce limit by node.val as we descend. If a leaf has the remaining limit > 0, it is insufficient.

Algorithm

Define dfs(node, limit):

1. If node is None, return None.
2. Recursively prune left and right subtrees with limit - node.val.
3. If the node is a leaf after pruning and limit > node.val, return None (insufficient).
4. Otherwise return node.

Correctness

After pruning children, if a node has no children (leaf) and the current path sum from root through this node is less than limit, the node is removed.

If either child survives, the node is necessary (there is at least one sufficient path through it).

Edge Cases

• A missing child should not contribute a fake value to min/max or path computations.
• Leaf nodes often define the base case; verify the behavior on a single-node tree.
• When passing state down the tree, update it before visiting children that depend on the current node.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from typing import Optional

class Solution:
    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:
        if root is None:
            return None

        if root.left is None and root.right is None:
            return None if root.val < limit else root

        root.left = self.sufficientSubset(root.left, limit - root.val)
        root.right = self.sufficientSubset(root.right, limit - root.val)

        if root.left is None and root.right is None:
            return None

        return root

Testing

def run_tests():
    s = Solution()

    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(3)), TreeNode(3))
    result = s.sufficientSubset(root, 4)
    assert result is not None

    root2 = TreeNode(5, TreeNode(-3), TreeNode(-2))
    result2 = s.sufficientSubset(root2, 6)

    print("all tests passed")

run_tests()