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:
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:
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:
Input: root = [1,2,-3,-5,null,4,null], limit = -1 Output: [1,null,-3,4]
Constraints:
[1, 5000].-105 <= Node.val <= 105-109 <= limit <= 109Problem Overview: You are given a binary tree and a limit value. A node is considered insufficient if every root-to-leaf path passing through it has a sum strictly less than the limit. Your task is to remove all such nodes and return the remaining tree.
This is a classic pruning problem on a tree. The key challenge is determining whether a node belongs to at least one valid root‑to‑leaf path whose sum is greater than or equal to the limit.
Approach 1: Recursive Depth-First Search (DFS) Pruning (Time: O(n), Space: O(h))
The most natural solution uses a recursive depth-first search. Traverse the tree from the root while maintaining the cumulative path sum. When you reach a leaf node, check whether the total sum is less than the limit. If it is, that leaf is insufficient and should be removed. During the recursion unwind, if both children of a node become null, the current node also becomes insufficient and must be pruned. This bottom‑up pruning ensures that nodes remain only if they lead to a valid root‑to‑leaf path.
The algorithm touches each node exactly once. The recursion depth is proportional to the height of the tree, giving O(n) time and O(h) space complexity. This approach is concise and aligns well with the recursive structure of a binary tree. Most interview solutions follow this pattern.
Approach 2: Iterative DFS Using Stack (Time: O(n), Space: O(n))
An iterative alternative simulates DFS using an explicit stack. Each stack entry stores the current node, the accumulated path sum, and references needed to update the parent. As you process nodes, push children with updated sums. When reaching leaves, determine whether the path satisfies the limit. If not, mark the node for removal and update its parent accordingly.
This method avoids recursion and may be useful in environments where recursion depth is limited. However, the bookkeeping is more complex because you must track parent-child relationships and update pointers after determining whether a subtree is valid. The time complexity remains O(n) since each node is processed once, while space can grow to O(n) in the worst case due to the explicit stack.
Recommended for interviews: The recursive DFS pruning approach. Interviewers expect you to recognize that insufficient nodes can only be determined after exploring all root‑to‑leaf paths below them. Demonstrating a clean post‑order DFS that removes children first and then evaluates the current node shows strong understanding of tree recursion.
This approach involves using a recursive post-order traversal (DFS) for the binary tree. The idea is to traverse each path from the root to the leaf and calculate the sum of the path. If at any node, the maximum path sum from this node to any leaf is less than the given limit, then this node along with its subtree should be considered insufficient and be removed.
During the traversal, if a node is found to be 'insufficient' (i.e., it does not meet the condition for any of the paths passing through it), it will be set to null.
This C function performs a recursive DFS to check and update each node in the tree. When examining a node, it recursively checks its left and right children with the updated sum limit, reducing the limit by the current node's value. If a node's children are determined to be insufficient (both become NULL), the node itself becomes NULL if it is also insufficient.
Time Complexity: O(n), where n is the number of nodes in the tree, because each node is visited once.
Space Complexity: O(h), where h is the height of the tree, due to recursion stack space.
In this approach, we simulate the DFS using an iterative method with a stack. The main idea is to employ a stack to keep track of nodes along with their path sums, allowing us to prune insufficient nodes without using recursion. This approach can help avoid deep recursion stack issues and might be beneficial for very unbalanced trees.
As nodes are processed, we update their sum limits to check path contribution and adjust subtree references in the result tree to prune insufficient paths.
This Python solution uses a manual stack to replace recursive DFS. Each node pushed onto the stack also tracks if it's a left or right child and its current path sum. We prune nodes based on path sums when each leaf is processed. If both children are pruned, the node itself is adjusted to remove these paths, maintaining correct parent-child relationships.
Python
JavaScript
Time Complexity: O(n), all nodes are processed using iterative stack DFS.
Space Complexity: O(n), due to the maximum size of the stack and mapping space for node path sums.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) | Time Complexity: O(n), where n is the number of nodes in the tree, because each node is visited once. Space Complexity: O(h), where h is the height of the tree, due to recursion stack space. |
| Iterative Approach Using Stack | Time Complexity: O(n), all nodes are processed using iterative stack DFS. Space Complexity: O(n), due to the maximum size of the stack and mapping space for node path sums. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search (DFS) Pruning | O(n) | O(h) | Best general solution for binary trees. Clean recursive logic and minimal code. |
| Iterative DFS Using Stack | O(n) | O(n) | When recursion depth might exceed stack limits or iterative traversal is preferred. |
Insufficient Nodes in Root to Leaf Paths (Leetcode 1080) • Coding Interviews • 1,556 views views
Watch 9 more video solutions →Practice Insufficient Nodes in Root to Leaf Paths with our built-in code editor and test cases.
Practice on FleetCode