# 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

| Item | Meaning |
|---|---|
| Input | Root of a binary tree and integer `limit` |
| Output | Root after removing insufficient nodes |

Function shape:

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

## Examples

Example 1:

```python
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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each node visited once |
| Space | `O(h)` | Recursion stack |

## 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

```python
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

```python
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()
```

| Test | Verification | Why |
|---|---|---|
| Root with children | Check structure | Some paths may be pruned |
| Root sum below limit | Entire tree may be pruned | All paths insufficient |