Skip to main content

Prune Subtrees Below Threshold

easy
Binary TreeTreeDepth First SearchDfs Recursive
Asked atAmazonGoogleMeta

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.