LeetCode 1080 - Insufficient Nodes in Root to Leaf Paths

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to prune a binary tree by removing insufficient nodes. A node is insufficient if every root-to-leaf path passing through it has a sum strictly less than the given limit. The input is the root of a binary tree and an integer limit. The output should be the root of the pruned tree, where all insufficient nodes have been removed.

The tree is defined with standard TreeNode objects, where each node has a val, a left child, and a right child. A leaf node is a node without any children. The constraints indicate that the tree can have up to 5000 nodes, and node values and the limit can be negative, which means we cannot assume all positive sums or simple pruning based on positive thresholds.

Important edge cases include trees with a single node, trees where all paths are insufficient, trees with negative values, and trees where pruning cascades upward (removing a leaf may render its parent insufficient). The problem guarantees at least one node exists, so we do not need to handle an empty tree initially.

Approaches

The brute-force approach would recursively calculate all root-to-leaf path sums, record which nodes belong to paths with sums below the limit, and then remove those nodes. This approach is correct but inefficient because it recalculates path sums multiple times for overlapping subtrees, leading to high redundant computation.

The optimal approach leverages post-order depth-first search (DFS). The key insight is that we can determine whether a node is insufficient by recursively checking its children. For a leaf, the path sum is simply its value. For an internal node, if both children are removed after recursion, then the node itself becomes insufficient if the path sum to it is below the limit. This allows pruning bottom-up in a single traversal, avoiding redundant calculations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Compute all root-to-leaf sums separately, prune nodes afterwards
Optimal	O(n)	O(h)	Single post-order DFS traversal; `h` is the tree height

Algorithm Walkthrough

Start at the root and perform a post-order DFS: visit the left child, then the right child, then the current node. This ensures decisions about pruning children are made before considering the parent.
For each node, recursively call the function on the left and right children with an updated remaining_limit (subtracting the node's value from the limit). This represents the remaining sum needed along this path to reach the limit.
After visiting children, check if the left or right child has become None. If so, this child is insufficient and is pruned by setting it to None.
If both children are None and the node is a leaf (or all paths through it are insufficient), check if the node's value is less than the remaining limit. If yes, return None to prune this node.
Return the node if it is sufficient (it has at least one child or its value meets the path requirement).

Why it works: Post-order traversal ensures children are processed before the parent, allowing bottom-up pruning. By reducing the limit along each path, we directly compute whether a path including the current node can meet the requirement without recomputing sums.

Python Solution

# 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]:
        def dfs(node: Optional[TreeNode], remaining: int) -> Optional[TreeNode]:
            if not node:
                return None
            # Leaf node
            if not node.left and not node.right:
                return node if node.val >= remaining else None
            # Recur for left and right with reduced remaining sum
            node.left = dfs(node.left, remaining - node.val)
            node.right = dfs(node.right, remaining - node.val)
            # If both children are pruned, check this node
            if not node.left and not node.right:
                return None
            return node
        
        return dfs(root, limit)

The implementation uses a helper dfs function that carries the remaining sum needed. Leaf nodes are checked directly, and internal nodes update their children references based on the recursive results. Post-order traversal ensures correct pruning from bottom up.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sufficientSubset(root *TreeNode, limit int) *TreeNode {
    var dfs func(node *TreeNode, remaining int) *TreeNode
    dfs = func(node *TreeNode, remaining int) *TreeNode {
        if node == nil {
            return nil
        }
        if node.Left == nil && node.Right == nil {
            if node.Val >= remaining {
                return node
            }
            return nil
        }
        node.Left = dfs(node.Left, remaining - node.Val)
        node.Right = dfs(node.Right, remaining - node.Val)
        if node.Left == nil && node.Right == nil {
            return nil
        }
        return node
    }
    return dfs(root, limit)
}

The Go implementation is almost identical to Python. We handle nil for empty nodes, pass the remaining sum recursively, and update the node's children after recursive calls. Go requires explicit nil checks and assignment back to children.

Worked Examples

Example 1: root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1

Start at root 1, remaining = 1
Recur left to node 2, remaining = 0
Recur left to node 4, remaining = -2
Leaf 8 ≥ -2, keep
Leaf 9 ≥ -2, keep
Node 4 keeps both children → keep node
Recur right to node -99 → paths insufficient, pruned
Node 2 keeps left child only → keep node
Recur right subtree similarly → prune insufficient nodes
Final tree: [1,2,3,4,null,null,7,8,9,null,14]

Example 2: root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22

Post-order DFS evaluates sums along paths
Node 1 and 3 are pruned as their paths < 22
Node 4 keeps left child 5 only
Final tree: [5,4,8,11,null,17,4,7,null,null,null,5]

Example 3: root = [1,2,-3,-5,null,4,null], limit = -1

Node -5 pruned, node 2 becomes insufficient, pruned
Node -3 keeps child 4
Final tree: [1,null,-3,4]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited exactly once in post-order DFS
Space	O(h)	Recursion stack depth proportional to tree height `h`, O(log n) for balanced, O(n) for skewed

The algorithm is efficient because it avoids recalculating sums multiple times. Bottom-up pruning ensures minimal traversal.

Test Cases

# Provided examples
assert Solution().sufficientSubset(build_tree([1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14]), 1) == build_tree([1,2,3,4,None,None,7,8,9,None,14])
assert Solution().sufficientSubset(build_tree([5,4,8,11,None,17,4,7,1,None,None,5,3]), 22) == build_tree([5,4,8,11,None,17,4,7,None,None,None,5])
assert Solution().sufficientSubset(build_tree([1,2,-3,-5,None,4,None]), -1) == build_tree([1,None,-3,4])

# Edge cases
assert Solution().sufficientSubset(build_tree([1]), 2) == None  # Single node insufficient
assert Solution().sufficientSubset(build_tree([1]), 1) == build_tree([1])  # Single node sufficient
assert Solution().sufficientSubset(build_tree([1,-2,-3,1,3,-2,None,-1]), -1) == build_tree([1,-2,None,1,None,None,None,-1])  # Mixed negative values

Test	Why
Single-node insufficient	Validates pruning of entire tree
Single-node sufficient	Validates keeping the tree when threshold met
Mixed negative values	Ensures algorithm correctly handles negative sums along paths

Edge Cases

Single-node tree: When the tree has only one node, the node itself may be pruned or kept based on its value relative to the limit. The implementation directly checks leaf nodes, handling this correctly.

All paths insufficient: If every root-to-leaf path sum is below the