Insufficient Nodes in Root to Leaf Paths

Remove leaf nodes where the sum from root to leaf is less than a given limit.

This problem asks you to prune a binary tree. You get a binary tree and a limit value. Any leaf node where the sum of values along the path from root to that leaf is strictly less than the limit should be removed.

When you remove a leaf, its parent might become a new leaf. If that new leaf also has a path sum less than the limit, you must remove it too.

The algorithm works recursively:

• For each node, calculate the remaining budget after subtracting the current node’s value
• Recursively process left and right subtrees with this reduced budget
• After processing children, check if current node becomes a leaf (both children were pruned)
• If it’s now a leaf and the remaining budget is positive, remove it too

def sufficientSubset(root, limit):
    def dfs(node, remaining):
        if not node:
            return None
        
        # If it's a leaf node
        if not node.left and not node.right:
            if remaining - node.val > 0:
                return None  # Remove this insufficient leaf
            else:
                return node  # Keep this sufficient leaf
        
        # Process children with reduced budget
        node.left = dfs(node.left, remaining - node.val)
        node.right = dfs(node.right, remaining - node.val)
        
        # If both children were pruned and we're now a leaf
        if not node.left and not node.right:
            return None
        
        return node
    
    return dfs(root, limit)

The key insight is that pruning happens bottom-up. A node that was originally internal might become a leaf after its children get pruned. You need to check this recursively until no more pruning is possible.

Time complexity: O(n) where n is the number of nodes. Space complexity: O(h) for recursion stack where h is the height of the tree.