Prune Subtrees Below Threshold
Problem Description
Given the root of a binary tree where every node holds a non-negative integer value, and a non-negative integer `cutoff`, remove every subtree whose **total sum of node values is strictly less than `cutoff`**.
Return the root of the pruned tree (which may be `null` if the entire tree is pruned).
**Example 1:**
```
Input: root = [8, 3, 12, 1, 2, null, 4], cutoff = 5
Tree structure:
8
/ \
3 12
/ \ \
1 2 4
Subtree rooted at node(1): sum = 1 < 5 → prune
Subtree rooted at node(2): sum = 2 < 5 → prune
Subtree rooted at node(3): sum = 3+1+2 = 6 >= 5 → keep (but children pruned)
Subtree rooted at node(4): sum = 4 < 5 → prune
Subtree rooted at node(12): sum = 12+4 = 16 >= 5 → keep (but right child pruned)
Output: [8, 3, 12]
```
**Example 2:**
```
Input: root = [10, 2, 3], cutoff = 4
Output: [10, 2, 3]
```
**Constraints:**
- The number of nodes in the tree is in the range `[1, 500]`.
- `0 <= Node.val <= 200`
- `0 <= cutoff <= 10000`
Constraints
- 1 <= number of nodes <= 500
- 0 <= Node.val <= 200
- 0 <= cutoff <= 10000
Follow-up
Extend the problem so that instead of a single global `cutoff`, each node specifies its own minimum subtree-sum threshold in a parallel array.
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.