# Insufficient Nodes in Root to Leaf Paths
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/insufficient-nodes-in-root-to-leaf-paths)
Canonical: https://scaleengineer.com/dsa/problems/insufficient-nodes-in-root-to-leaf-paths
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
---
## Problem
Given the `root` of a binary tree and an integer `limit`, delete all **insufficient nodes** in the tree simultaneously, and return _the root of the resulting binary tree_.

A node is **insufficient** if every root to **leaf** path intersecting this node has a sum strictly less than `limit`.

A **leaf** is a node with no children.

**Example 1:**

![](https://assets.glich.co/dsa/insufficient-nodes-in-root-to-leaf-paths/image0.png) 

**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 2:**

![](https://assets.glich.co/dsa/insufficient-nodes-in-root-to-leaf-paths/image1.png) 

**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 3:**

![](https://assets.glich.co/dsa/insufficient-nodes-in-root-to-leaf-paths/image2.png) 

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

**Constraints:**

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

# Approaches
## Two-Pass DFS Traversal
This approach uses two separate traversals of the binary tree. The first pass is to identify and mark every node that lies on at least one 'sufficient' root-to-leaf path (a path with sum >= limit). The second pass then uses this information to reconstruct the tree, pruning any node that was not marked as sufficient.
**Time:** O(N), where N is the number of nodes. The first pass visits each node once, and the second pass also visits each node once, leading to a total time complexity of O(N) + O(N) = O(N). · **Space:** O(N), where N is the number of nodes in the tree. This is because we use a hash map to store the sufficiency status for every node.
**Pros:** The logic is separated into two distinct, clear steps: identification and modification, which can be easier to reason about.
**Cons:** Requires O(N) extra space for the hash map, making it less space-efficient than the single-pass approach.; Involves two separate traversals of the tree, which is less elegant and slightly more complex to implement.
### Explanation
In this method, we first need to determine for every single node whether it's part of a sufficient path. A node is sufficient if at least one root-to-leaf path passing through it has a sum greater than or equal to `limit`. We can use a post-order traversal to compute this for all nodes and store the results in a hash map.

Once we have this information, we perform a second traversal (e.g., pre-order) to build the new tree. During this traversal, if we encounter a node that our map indicates is insufficient, we prune it by returning `null` to its parent. Otherwise, we keep the node and continue the process for its children.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    private Map<TreeNode, Boolean> sufficientMap = new HashMap<>();
    private int limit;

    public TreeNode sufficientSubset(TreeNode root, int limit) {
        this.limit = limit;
        if (root == null) {
            return null;
        }
        
        // Pass 1: Populate the map with sufficiency information for each node.
        isNodeSufficient(root, 0);
        
        // Pass 2: Rebuild the tree by pruning insufficient nodes.
        return rebuild(root);
    }

    // Pass 1: Returns true if the subtree at 'node' contains a sufficient path.
    private boolean isNodeSufficient(TreeNode node, long sum) {
        if (node == null) {
            return false;
        }

        sum += node.val;
        
        if (node.left == null && node.right == null) { // Leaf node
            boolean sufficient = sum >= limit;
            sufficientMap.put(node, sufficient);
            return sufficient;
        }

        boolean leftSufficient = isNodeSufficient(node.left, sum);
        boolean rightSufficient = isNodeSufficient(node.right, sum);
        
        // A node is on a sufficient path if any of its descendant paths are sufficient.
        boolean isSufficient = leftSufficient || rightSufficient;
        sufficientMap.put(node, isSufficient);
        return isSufficient;
    }

    // Pass 2: Returns the modified tree node, or null if it should be pruned.
    private TreeNode rebuild(TreeNode node) {
        if (node == null) {
            return null;
        }
        
        // If a node is not on any sufficient path, prune it.
        if (!sufficientMap.getOrDefault(node, false)) {
            return null;
        }
        
        node.left = rebuild(node.left);
        node.right = rebuild(node.right);
        
        return node;
    }
}
```
### Algorithm
- Create a `Map<TreeNode, Boolean>` to store whether a node is part of a sufficient path.
- **Pass 1: Mark Sufficient Nodes**
  - Implement a recursive DFS function `isNodeSufficient(node, currentSum)`.
  - This function traverses the tree in a post-order fashion.
  - For a leaf node, it checks if the path sum `currentSum + node.val` is `>= limit`. It stores this boolean result in the map and returns it.
  - For an internal node, it recursively calls itself for its left and right children.
  - A node is considered sufficient if either its left or right subtree contains a sufficient path (`leftSufficient || rightSufficient`). This result is stored in the map and returned.
  - Initiate this pass by calling `isNodeSufficient(root, 0)`.
- **Pass 2: Rebuild the Tree**
  - Implement a second recursive function `rebuild(node)`.
  - This function traverses the tree and constructs the final version.
  - For each `node`, it checks the map. If the map indicates the node is insufficient (`sufficientMap.get(node)` is false), it returns `null`, effectively pruning this node and its entire subtree.
  - If the node is sufficient, it recursively calls `rebuild` for its children: `node.left = rebuild(node.left)` and `node.right = rebuild(node.right)`.
  - The final result is the tree returned by `rebuild(root)`.

## Single-Pass Post-Order Traversal
This optimal approach solves the problem in a single post-order traversal of the tree. A recursive function is used to simultaneously check for path sufficiency and prune the tree in-place. The decision to keep or remove a node is made after visiting its children, which is the essence of a post-order traversal.
**Time:** O(N), where N is the number of nodes in the tree, as we visit each node exactly once. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, this can be O(N).
**Pros:** Highly efficient, solving the problem in a single pass.; Space complexity is optimal, only using O(H) space for the recursion stack.; Modifies the tree in-place, avoiding the need for extra data structures to store intermediate results.
**Cons:** The recursive function has a side effect (modifying the tree), which can sometimes make the code slightly harder to reason about compared to a pure function.; The combined logic of checking and pruning in a single function can be less intuitive for beginners.
### Explanation
We can determine if a node is insufficient and prune it in a single pass. The key idea is that a node's sufficiency depends on its children. This suggests a post-order traversal approach.

We define a recursive helper function that takes a node and the sum of the path from the root to its parent. This function will do two things: prune the children if they are roots of insufficient subtrees, and return a boolean indicating if the current node is part of any sufficient path.

For any node, we first recurse on its children. The boolean returned from the recursive calls tells us if a sufficient path exists through the left or right child. If a child's recursive call returns `false`, it means all paths through that child are insufficient, so we can prune that child by setting the parent's link to `null`. After handling the children, the current node is sufficient if at least one of its children was on a sufficient path. The base case is a leaf node, where we simply check if its root-to-leaf path sum meets the `limit`.

```java
class Solution {
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        // The helper function returns false if the entire tree starting from root is insufficient.
        if (!isSufficient(root, 0, limit)) {
            return null;
        }
        return root;
    }

    /**
     * Performs post-order traversal to prune insufficient nodes.
     * @param node The current node.
     * @param sum The sum of values from the root to the parent of `node`.
     * @param limit The threshold.
     * @return true if `node` is part of a sufficient path, false otherwise.
     */
    private boolean isSufficient(TreeNode node, long sum, int limit) {
        if (node == null) {
            return false;
        }

        // If it's a leaf node, check if the path sum is sufficient. This is the base case.
        if (node.left == null && node.right == null) {
            return (sum + node.val) >= limit;
        }

        // Recursively check left and right subtrees. The sum for the children's path
        // includes the current node's value.
        boolean leftIsSufficient = isSufficient(node.left, sum + node.val, limit);
        boolean rightIsSufficient = isSufficient(node.right, sum + node.val, limit);

        // If the left subtree does not have any sufficient path, prune it.
        if (!leftIsSufficient) {
            node.left = null;
        }

        // If the right subtree does not have any sufficient path, prune it.
        if (!rightIsSufficient) {
            node.right = null;
        }

        // The current node is part of a sufficient path if either of its subtrees
        // (after pruning) contains a sufficient path.
        return leftIsSufficient || rightIsSufficient;
    }
}
```
### Algorithm
- Define a single recursive helper function, e.g., `isSufficient(node, sum, limit)`, that returns a boolean.
- This function will perform a post-order traversal. For a given `node`, it first makes recursive calls for its left and right children.
- The `sum` parameter tracks the sum of node values from the root to the parent of the current `node`.
- **Base Case**: If `node` is a leaf (`node.left == null && node.right == null`), the function checks if the total path sum (`sum + node.val`) is `>= limit`. It returns `true` if sufficient, `false` otherwise.
- **Recursive Step**: For an internal node:
  - Recursively call `isSufficient` for the left child: `leftSufficient = isSufficient(node.left, sum + node.val, limit)`. Handle the case where `node.left` is null (which should result in `false`).
  - Recursively call `isSufficient` for the right child: `rightSufficient = isSufficient(node.right, sum + node.val, limit)`.
  - After the recursive calls return, use their boolean results to prune the tree. If `leftSufficient` is `false`, set `node.left = null`. If `rightSufficient` is `false`, set `node.right = null`.
  - The function then returns `leftSufficient || rightSufficient`. This boolean indicates to the parent caller whether the current `node` remains part of a sufficient path after potential pruning of its children.
- In the main function, call `isSufficient(root, 0, limit)`. If this initial call returns `false`, it means the root itself is insufficient, so the entire tree is deleted. In this case, return `null`. Otherwise, return the modified `root`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode sufficientSubset ( TreeNode root , int limit ) { if ( root == null ) { return null ; } limit -= root . val ; if ( root . left == null && root . right == null ) { return limit > 0 ? null : root ; } root . left = sufficientSubset ( root . left , limit ); root . right = sufficientSubset ( root . right , limit ); return root . left == null && root . right == null ? null : root ; } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} limit * @return {TreeNode} */ var sufficientSubset =
  function (root, limit) {
    if (root === null) {
      return null;
    }
    limit -= root.val;
    if (root.left === null && root.right === null) {
      return limit > 0 ? null : root;
    }
    root.left = sufficientSubset(root.left, limit);
    root.right = sufficientSubset(root.right, limit);
    return root.left === null && root.right === null ? null : root;
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * sufficientSubset ( TreeNode * root , int limit ) { if ( ! root ) { return nullptr ; } limit -= root -> val ; if ( ! root -> left && ! root -> right ) { return limit > 0 ? nullptr : root ; } root -> left = sufficientSubset ( root -> left , limit ); root -> right = sufficientSubset ( root -> right , limit ); return ! root -> left && ! root -> right ? nullptr : root ; } };
```

### Python

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