1080. Insufficient Nodes in Root to Leaf Paths Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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].
-10⁵ <= Node.val <= 10⁵
-10⁹ <= limit <= 10⁹

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.

Python

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: TreeNode, limit: int) -> TreeNode:
        if not root:
            return None
        if not root.left and not root.right:
            return None if root.val < limit else root
        root.left = self.sufficientSubset(root.left, limit - root.val)
        root.right = self.sufficientSubset(root.right, limit - root.val)
        return None if not root.left and not root.right else root

Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class SufficientSubset {
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        if (root == null) return null;
        if (root.left == null && root.right == null) return root.val < limit ? null : root;
        root.left = sufficientSubset(root.left, limit - root.val);
        root.right = sufficientSubset(root.right, limit - root.val);
        return (root.left == null && root.right == null) ? null : root;
    }
}

C++

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* sufficientSubset(TreeNode* root, int limit) {
    if (!root) return nullptr;
    if (!root->left && !root->right) return root->val < limit ? nullptr : root;
    root->left = sufficientSubset(root->left, limit - root->val);
    root->right = sufficientSubset(root->right, limit - root->val);
    return (!root->left && !root->right) ? nullptr : root;
}

JavaScript

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var sufficientSubset = function(root, limit) {
    if (!root) return null;
    if (!root.left && !root.right) return root.val < limit ? null : root;
    root.left = sufficientSubset(root.left, limit - root.val);
    root.right = sufficientSubset(root.right, limit - root.val);
    return (!root.left && !root.right) ? null : root;
};

#include <stdio.h>
#include <stdlib.h>

// Definition for a binary tree node.
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* sufficientSubset(TreeNode* root, int limit) {
    if (!root) return NULL;
    if (!root->left && !root->right) return root->val < limit ? NULL : root;
    root->left = sufficientSubset(root->left, limit - root->val);
    root->right = sufficientSubset(root->right, limit - root->val);
    return !root->left && !root->right ? NULL : root;
}

// Assume helper functions for node creation are here (e.g., insert, etc.)

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode SufficientSubset(TreeNode root, int limit) {
        if (root == null) return null;
        if (root.left == null && root.right == null) return root.val < limit ? null : root;
        root.left = SufficientSubset(root.left, limit - root.val);
        root.right = SufficientSubset(root.right, limit - root.val);
        return (root.left == null && root.right == null) ? null : root;
    }
}

The Python function employs a recursive depth-first strategy to evaluate each path in the tree. For each leaf node, it checks if the current path sum is less than the limit and prunes nodes accordingly. It ensures nodes are only retained if their subtree contains a valid path sum to a leaf.

Complexity

Time Complexity: O(n), where n denotes the number of nodes in the tree.

Space Complexity: O(h), where h is the tree’s height, accounting for the recursion stack.

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.

Python

class Solution:
    def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
        if not root:
            return None
        stack = [(root, None, None)]
        path_map = {root: root.val}
        while stack:
            node, parent, is_left = stack.pop()
            path_sum = path_map[node]
            if node.left is None and node.right is None:
                if path_sum < limit:
                    if parent:
                        if is_left:
                            parent.left = None
                        else:
                            parent.right = None
                    else:
                        return None
            if node.right:
                path_map[node.right] = path_sum + node.right.val
                stack.append((node.right, node, False))
            if node.left:
                path_map[node.left] = path_sum + node.left.val
                stack.append((node.left, node, True))
        return root

JavaScript

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var sufficientSubset = function(root, limit) {
    if (!root) return null;
    let stack = [[root, null, false]], pathMap = new Map();
    pathMap.set(root, root.val);
    while (stack.length) {
        let [node, parent, isLeft] = stack.pop();
        let pathSum = pathMap.get(node);
        if (!node.left && !node.right) {
            if (pathSum < limit) {
                if (parent) {
                    if (isLeft) parent.left = null;
                    else parent.right = null;
                } else {
                    return null;
                }
            }
        }
        if (node.right) {
            pathMap.set(node.right, pathSum + node.right.val);
            stack.push([node.right, node, false]);
        }
        if (node.left) {
            pathMap.set(node.left, pathSum + node.left.val);
            stack.push([node.left, node, true]);
        }
    }
    return root;
};

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.

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

TypeScript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function sufficientSubset(root: TreeNode | null, limit: number): TreeNode | null {
    if (root === null) {
        return null;
    }
    limit -= root.val;
    if (root.left === null && root.right === null) {
        return limit > 0 ? null : root;
    }
    root.left = sufficientSubset(root.left, limit);
    root.right = sufficientSubset(root.right, limit);
    return root.left === null && root.right === null ? null : root;
}

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

	limit -= root.Val
	if root.Left == nil && root.Right == nil {
		if limit > 0 {
			return nil
		}
		return root
	}

	root.Left = sufficientSubset(root.Left, limit)
	root.Right = sufficientSubset(root.Right, limit)

	if root.Left == nil && root.Right == nil {
		return nil
	}
	return root
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Recursive Depth-First Search (DFS)	Time Complexity: O(n), where n denotes the number of nodes in the tree. Space Complexity: O(h), where h is the tree’s height, accounting for the recursion stack.
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

Complexity

Recursive Depth-First Search (DFS)

Time Complexity: O(n), where n denotes the number of nodes in the tree.

Space Complexity: O(h), where h is the tree’s height, accounting for the recursion stack.

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

–

Complexity analysis

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.

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.

Insufficient Nodes in Root to Leaf Paths solution and explanation

The problem

Approach overview

Approach 1: Recursive Depth-First Search (DFS)

Approach 2: Iterative Approach Using Stack

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Insufficient Nodes in Root to Leaf Paths solution and explanation

The problem

Approach overview

Approach 1: Recursive Depth-First Search (DFS)

Approach 2: Iterative Approach Using Stack

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems