Code Implementation

# 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: TreeNode, limit: int) -> TreeNode:
        def dfs(node, curr_sum):
            if not node:
                return None
            curr_sum += node.val
            if not node.left and not node.right:
                # Leaf node: check if path sum is sufficient
                return node if curr_sum >= limit else None
            node.left = dfs(node.left, curr_sum)
            node.right = dfs(node.right, curr_sum)
            # If both children are pruned, prune this node as well
            if not node.left and not node.right:
                return None
            return node
        return dfs(root, 0)
      

/**
 * 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;
        if (!root->left && !root->right) {
            return (root->val >= limit) ? root : nullptr;
        }
        root->left = sufficientSubset(root->left, limit - root->val);
        root->right = sufficientSubset(root->right, limit - root->val);
        if (!root->left && !root->right) return nullptr;
        return root;
    }
};
      

/**
 * 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;
        if (root.left == null && root.right == null) {
            return root.val >= limit ? root : null;
        }
        root.left = sufficientSubset(root.left, limit - root.val);
        root.right = sufficientSubset(root.right, limit - root.val);
        if (root.left == null && root.right == null) return null;
        return root;
    }
}
      

/**
 * 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) {
    function dfs(node, currSum) {
        if (!node) return null;
        currSum += node.val;
        if (!node.left && !node.right) {
            return currSum >= limit ? node : null;
        }
        node.left = dfs(node.left, currSum);
        node.right = dfs(node.right, currSum);
        if (!node.left && !node.right) return null;
        return node;
    }
    return dfs(root, 0);
};
      

Problem Description

You are given the root of a binary tree and an integer limit. Each root-to-leaf path in the tree has a sum (the sum of all node values along that path). Your task is to prune the tree by removing all insufficient nodes — that is, any node where every root-to-leaf path passing through it has a sum less than limit. After pruning, return the root of the resulting tree.

A node is insufficient if all root-to-leaf paths through it sum to less than limit. If a node is removed, all its descendants are removed as well. If the entire tree is insufficient, return null.

Constraints: The tree has at most one valid solution. You must not reuse elements, and the pruning should be done in-place (modify the tree structure).

Thought Process

To solve this problem, we need to identify and remove nodes that cannot participate in any root-to-leaf path with a sum at least equal to limit.

The brute-force way would be to enumerate all root-to-leaf paths, calculate their sums, and then somehow mark all nodes that are only on insufficient paths. However, this is inefficient and not scalable for large trees.

Instead, we can use a recursive approach: for each node, we check if any path from that node to a leaf is sufficient. If not, we prune that node. This is a classic case for depth-first search (DFS) because we need to process children before their parent can decide whether to keep or prune itself.

The key insight is that a node is only insufficient if all its root-to-leaf paths are insufficient. So, if both its left and right children are pruned away, we should prune the node as well.

Solution Approach

We will use a post-order DFS traversal to solve the problem. Here is the step-by-step approach:

1. Recursive Traversal: For each node, recursively process its left and right children first.
2. Leaf Node Check: When we reach a leaf node, check if the sum from the root to this leaf is at least limit. If not, prune (remove) this node by returning null.
3. Prune Internal Nodes: After processing both children, if both are pruned (i.e., both are null), it means all paths through this node are insufficient, so prune this node as well.
4. Update Children: Set the left and right pointers of the current node to the possibly-pruned results of the recursive calls.
5. Return the Possibly-Pruned Node: If the node is not pruned, return it; otherwise, return null.

We use DFS because it naturally allows us to process children before their parent, which is necessary for this bottom-up pruning.

Example Walkthrough

Example:

Consider the following tree and limit = 1:

        1
       / \
      2   -3
     /   /  \
   -5   4    -2
  

Let's walk through the pruning process:

• Starting at the root (1), we process the left child (2):
  • Process 2's left child (-5): it's a leaf. Path sum is 1 + 2 + (-5) = -2 which is less than 1, so prune -5.
  • 2 has no right child. Both children are now null, so prune 2.
• Process the right child (-3):
  • Left child 4: it's a leaf. Path sum is 1 + (-3) + 4 = 2 which is sufficient, so keep 4.
  • Right child -2: it's a leaf. Path sum is 1 + (-3) + (-2) = -4 which is insufficient, so prune -2.
  • -3 has at least one sufficient child (4), so keep -3.
• At the root (1), left child is null, right child is -3 (with child 4). The root is kept since there is at least one sufficient path.

The pruned tree is:

        1
         \
         -3
          /
         4
  

Time and Space Complexity

Brute-force Approach: Enumerating all root-to-leaf paths is exponential in the worst case (O(2^h) for height h), which is infeasible for large trees.

Optimized DFS Approach: Each node is visited exactly once, and at each node, we do constant work (checking sums, updating pointers).

• Time Complexity: O(N), where N is the number of nodes in the tree.
• Space Complexity: O(H), where H is the height of the tree (due to recursion stack). In the worst case (skewed tree), H = N.

Summary

The problem is elegantly solved by a post-order DFS traversal, pruning away insufficient nodes from the bottom up. The key insight is to only keep nodes that have at least one sufficient root-to-leaf path. With this approach, we efficiently prune the tree in a single traversal, using only O(H) space and O(N) time. This makes the solution both simple and optimal for large trees.