Insufficient Nodes in Root to Leaf Paths: Tree Pruning with DFS

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 tree. A node is insufficient if every root-to-leaf path passing through that node has a path sum strictly less than limit.

This is LeetCode 1080: Insufficient Nodes in Root to Leaf Paths. The tricky part is that you cannot decide whether to keep or delete a node by looking at it in isolation. You need to know the fate of its entire subtree first. A node survives only if at least one path through it meets the limit.

Example: Given the tree [1, 2, -3, 4, -5] and limit = 1, the root-to-leaf path sums are 7 (1+2+4), -2 (1+2+(-5)), and -2 (1+(-3)). After pruning, only the path with sum 7 remains.

Why this problem matters

Tree pruning is a recurring pattern in coding interviews. You see it in problems like Binary Tree Pruning (LeetCode 814) and Delete Nodes And Return Forest (LeetCode 1110). What makes this problem distinctive is that the pruning condition depends on global information (the running sum from the root), not just local node values.

This problem teaches you two things at once. First, post-order traversal for deletion: you must clean up the children before you can decide what to do with the parent. Second, path sum accumulation: you carry a running sum downward so that each leaf can check whether its path meets the threshold.

If you have solved Path Sum or Path Sum II, you already know how to carry a sum from root to leaf. This problem adds one more layer: using that sum to decide which nodes to remove.

The key insight

Use post-order DFS. At each node, recursively prune the left subtree and the right subtree first. Then decide whether the current node should survive.

For a leaf node, the decision is simple: if the running sum from the root to this leaf is less than limit, the leaf is insufficient and should be deleted (return None). If the sum is >= limit, keep it.

For an internal node, the decision depends on its children after pruning. If both children have been pruned away (both are None), it means every path through this node was insufficient. The node itself becomes a dead end and should also be deleted. If at least one child remains, the node stays.

The post-order structure is critical. You cannot decide the fate of a parent until you know what happened to its children. Pruning bottom-up ensures that by the time you evaluate a node, you already have the final answer for its subtrees.

The solution

def sufficientSubset(root, limit):
    def dfs(node, running_sum):
        if not node:
            return None

        running_sum += node.val

        if not node.left and not node.right:
            return None if running_sum < limit else node

        node.left = dfs(node.left, running_sum)
        node.right = dfs(node.right, running_sum)

        if not node.left and not node.right:
            return None

        return node

    return dfs(root, 0)

Here is how each piece works.

The running_sum parameter tracks the cumulative sum from the root down to the current node. Each recursive call adds the current node's value to this sum.

The leaf check comes first. When a node has no children, it is a leaf. You compare the full root-to-leaf sum against limit. If the sum falls short, return None to delete this leaf. Otherwise, return the node to keep it.

For non-leaf nodes, you recurse into both children first. This is the post-order part. The recursive calls return either the pruned child or None. You assign the results back to node.left and node.right, which handles the actual deletion.

After pruning both subtrees, you check whether both children are now None. If so, every path through this node was insufficient, so you delete this node too by returning None. If at least one child survived, the node stays.

Visual walkthrough

Let's trace through the tree [1, 2, -3, 4, -5] with limit = 1. The DFS visits nodes in post-order, pruning from the bottom up.

The DFS visited every node exactly once. At each leaf, it compared the full path sum to the limit. Leaves that fell short were deleted. Then, moving back up the tree, any internal node left with no children was also deleted. The final tree contains only nodes that lie on at least one sufficient path.

Complexity analysis

Time is O(n) where n is the number of nodes in the tree. The DFS visits each node exactly once, performing constant work at each node (one comparison and at most two recursive calls).

Space is O(h) where h is the height of the tree. This accounts for the recursion stack. In the worst case (a completely skewed tree), h = n and the space is O(n). For a balanced tree, h = log n.

The building blocks

1. Post-order tree pruning

The pattern of recursively processing children first, then deciding whether to keep or delete the current node. You use this any time a node's fate depends on what remains in its subtrees after cleanup. Binary Tree Pruning (LeetCode 814) uses the same structure: prune subtrees that contain only zeros, bottom-up. The template is always the same. Recurse left, recurse right, then check whether the current node should survive based on its children.

2. Path sum accumulation from root

The pattern of carrying a running sum downward through the tree. Each recursive call adds the current node's value. At leaves, the running sum equals the full root-to-leaf path sum. This is the same technique used in Path Sum (LeetCode 112) and Path Sum II (LeetCode 113). The only difference here is what you do with the sum at the leaf: instead of returning true or collecting the path, you use it to decide whether to prune.

Edge cases

• Single node tree: If the root is a leaf and its value is less than limit, the entire tree is deleted and you return None. If its value is >= limit, return the root unchanged.
• All paths insufficient: Every root-to-leaf path has a sum below the limit. The entire tree gets pruned, and you return None. This happens naturally because post-order pruning deletes all leaves first, then their parents become leaves and get deleted too, cascading all the way up.
• No paths insufficient: Every root-to-leaf path meets the limit. No nodes are deleted, and the tree is returned unchanged.
• Skewed tree (single path): A tree that is just a chain has exactly one root-to-leaf path. Either the entire chain survives or the entire chain is deleted.
• Path sum exactly equals limit: A path with sum equal to limit is not insufficient (the condition is strictly less than). The leaf and all nodes on that path survive, assuming no other pruning removes them.

From understanding to recall

You have seen how post-order DFS naturally solves the "prune insufficient nodes" problem. The structure is clean: recurse into children, let them prune themselves, then check if the current node still has a reason to exist. The running sum flows downward, and the pruning decisions flow upward.

But writing this under pressure, the details matter. Do you check the leaf condition before or after recursing? Do you return None or delete the node in place? Do you use strict less than or less than or equal to? These are the kinds of small decisions that cost time in an interview when you have not practiced them.

Spaced repetition burns in the pattern. You write the DFS helper, the leaf check, the post-order pruning logic, and the running sum from scratch at increasing intervals. After a few reps, you stop thinking about the order of operations. You just write it.

Related posts

• Path Sum - The foundational root-to-leaf path sum check
• Binary Tree Maximum Path Sum - Advanced path sum reasoning in trees
• Binary Tree Pruning - Similar tree pruning with a simpler condition

CodeBricks breaks problems like Insufficient Nodes into the post-order pruning and path sum accumulation building blocks behind them, then drills those blocks with spaced repetition until they are automatic. When a tree pruning problem appears in your interview, you will not need to rederive the approach. You will just write it.