Skip to main content
Talentd

Insufficient Nodes in Root to Leaf Paths - Solution & Explanation

MediumTreeDepth-First SearchBinary Tree15 min readAsked at: Amazon
Practice this problem

Problem Statement

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:

  • The number of nodes in the tree is in the range [1, 5000].
  • -105 <= Node.val <= 105
  • -109 <= limit <= 109

Approach Overview

Problem 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.

Approach 1: Recursive Depth-First Search (DFS)

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Iterative Approach Using Stack

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Depth-First Search (DFS) PruningO(n)O(h)Best general solution for binary trees. Clean recursive logic and minimal code.
Iterative DFS Using StackO(n)O(n)When recursion depth might exceed stack limits or iterative traversal is preferred.

Video Solution

Insufficient Nodes in Root to Leaf Paths (Leetcode 1080) • Coding Interviews • 1,583 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Insufficient Nodes in Root to Leaf Paths easy or hard?
The problem is generally rated Medium difficulty. The traversal itself is straightforward DFS, but the pruning logic requires thinking in post-order so that child nodes are processed before evaluating the parent. Understanding this bottom-up pruning pattern is the main challenge.
Insufficient Nodes in Root to Leaf Paths Python/Java solution
In Python or Java, implement a recursive DFS function that returns the updated subtree after pruning. Track the running path sum and check the limit when reaching leaves. If both left and right children become null after recursion and the path sum is insufficient, return null so the parent removes that node.
How to solve Insufficient Nodes in Root to Leaf Paths in O(n)?
Use a post-order DFS traversal. Pass the current path sum while descending the tree, and when reaching leaves check if the total sum is below the limit. If it is, return null to prune the node. After processing both children, remove the current node if both children become null and the node does not satisfy the limit condition. This ensures each node is processed exactly once.
What is the best approach for Insufficient Nodes in Root to Leaf Paths?
The best approach is a recursive depth-first search that prunes nodes after exploring their children. During DFS, keep track of the cumulative path sum and remove leaf nodes whose path sum is below the limit. When recursion returns, delete any parent node whose children were removed and which no longer leads to a valid path. This runs in O(n) time with O(h) recursion space.
Is Insufficient Nodes in Root to Leaf Paths asked at Google/Amazon/Meta?
Tree pruning and path-sum style problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variations of this problem test understanding of DFS, recursion, and binary tree traversal. Interviewers often expect a clean recursive solution with correct pruning logic.
What data structure is used in Insufficient Nodes in Root to Leaf Paths?
The core data structure is a binary tree. The solution typically uses depth-first search, implemented either with recursion or an explicit stack. The algorithm evaluates root-to-leaf paths and modifies the tree structure by removing insufficient nodes.
What is the time complexity of Insufficient Nodes in Root to Leaf Paths?
The optimal solution runs in O(n) time where n is the number of nodes in the binary tree. Each node is visited once during the DFS traversal and evaluated based on the accumulated path sum. The space complexity is O(h), where h is the tree height due to recursion stack usage.

Ready to solve this problem?

Practice Insufficient Nodes in Root to Leaf Paths with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Nodes Equal to Average of Subtree