Insufficient Nodes in Root to Leaf Paths - Practice Coding Problems

Insufficient Nodes in Root to Leaf Paths - Problem

Binary Tree Path Pruning Challenge

Imagine you're a gardener tasked with pruning a binary tree! 🌳 Given the root of a binary tree and an integer limit, you need to remove all "insufficient" nodes that don't contribute to any path meeting your minimum sum requirement.

📊 What makes a node insufficient?
A node is considered insufficient if every root-to-leaf path that passes through this node has a sum strictly less than the given limit.

🎯 Your Mission:
Delete all insufficient nodes simultaneously and return the root of the resulting tree. If even the root becomes insufficient, return null!

Key Points:
• A leaf node has no children
• Path sums are calculated from root to leaf
• All insufficient nodes are removed in one operation
• The tree structure must remain valid after pruning

Input & Output

example_1.py — Basic Tree Pruning

$ Input: root = [5,4,8,11,null,13,2], limit = 22

› Output: [5,4,8,null,13,null,2]

💡 Note: Node 11 is removed because all paths through it (5→4→11 = 20) are less than 22. The path 5→4→13 = 22 and 5→8→2 = 15 are sufficient paths, so those nodes remain.

example_2.py — Complete Tree Removal

$ 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]

💡 Note: All paths with negative values (-99) create insufficient sums. Only paths with positive contributions remain after pruning.

example_3.py — Single Node Edge Case

$ Input: root = [5], limit = 10

› Output: null

💡 Note: The single node has value 5, which is less than the limit 10, so the entire tree is removed.

Constraints

The number of nodes in the tree is in the range [1, 5000]
-10⁵ ≤ Node.val ≤ 10⁵
-10⁹ ≤ limit ≤ 10⁹
Each root-to-leaf path will have at least one node

Visualization

Tap to expand

Understanding the Visualization

Identify All Paths

Find every path from root to leaf and calculate their sums

Mark Insufficient Nodes

Nodes are insufficient if ALL paths through them are below the limit

Prune the Tree

Remove all insufficient nodes simultaneously, maintaining tree structure

Key Takeaway

🎯 Key Insight: Use post-order DFS to determine node sufficiency bottom-up. A node stays if it has at least one child that leads to a valid path, making this an O(n) optimal solution.

Asked in

G Google 42 a Amazon 38 f Meta 31 ⊞ Microsoft 27

The optimal solution uses post-order DFS traversal to process the tree bottom-up. For each node, we first recursively process its children, then decide whether to keep the current node based on whether it has any remaining children (indicating at least one sufficient path). This approach achieves O(n) time complexity by visiting each node exactly once, making it the most efficient solution for this tree pruning problem.

Common Approaches

Approach	Time	Space	Notes
✓ Post-Order DFS (Optimal)	O(n)	O(h)	Use bottom-up traversal to determine node sufficiency in one pass
Brute Force (All Paths Enumeration)	O(n²)	O(n²)	Generate all root-to-leaf paths, then remove nodes not in any valid path

Post-Order DFS (Optimal) — Algorithm Steps

Start from leaves and work upward (post-order)
For each leaf: check if root-to-leaf path sum >= limit
For each internal node: recursively process children first
Remove child if it returns null (insufficient)
Current node is sufficient if any path through it meets limit
Return null if current node is insufficient, otherwise return node

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Leaves

Check if each leaf's root-to-leaf sum meets the limit

Work Upward

For each internal node, process children first (post-order)

Make Decision

Keep node only if at least one child path is valid

Code -

solution.c — C

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

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

struct TreeNode* dfs(struct TreeNode* node, int currentSum, int limit) {
    if (!node) return NULL;
    
    currentSum += node->val;
    
    // Leaf node case
    if (!node->left && !node->right) {
        return currentSum >= limit ? node : NULL;
    }
    
    // Post-order traversal
    node->left = dfs(node->left, currentSum, limit);
    node->right = dfs(node->right, currentSum, limit);
    
    // Keep node if it has valid children
    if (node->left || node->right) {
        return node;
    }
    return NULL;
}

struct TreeNode* sufficientSubset(struct TreeNode* root, int limit) {
    return dfs(root, 0, limit);
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visits each node exactly once in post-order traversal

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h, O(log n) for balanced tree, O(n) for skewed tree

✓ Linear Space

33.7K Views

Medium Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Post-Order DFS (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler