Scale Engineer

Insufficient Nodes in Root to Leaf Paths

Med
#1026Time: O(N), where N is the number of nodes. The first pass visits each node once, and the second pass also visits each node once, leading to a total time complexity of O(N) + O(N) = O(N).Space: O(N), where N is the number of nodes in the tree. This is because we use a hash map to store the sufficiency status for every node.
Algorithms
Depth-First Search
Data structures
TreeBinary Tree

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses two separate traversals of the binary tree. The first pass is to identify and mark every node that lies on at least one 'sufficient' root-to-leaf path (a path with sum >= limit). The second pass then uses this information to reconstruct the tree, pruning any node that was not marked as sufficient.

Algorithm

  • Create a Map<TreeNode, Boolean> to store whether a node is part of a sufficient path.
  • Pass 1: Mark Sufficient Nodes
    • Implement a recursive DFS function isNodeSufficient(node, currentSum).
    • This function traverses the tree in a post-order fashion.
    • For a leaf node, it checks if the path sum currentSum + node.val is >= limit. It stores this boolean result in the map and returns it.
    • For an internal node, it recursively calls itself for its left and right children.
    • A node is considered sufficient if either its left or right subtree contains a sufficient path (leftSufficient || rightSufficient). This result is stored in the map and returned.
    • Initiate this pass by calling isNodeSufficient(root, 0).
  • Pass 2: Rebuild the Tree
    • Implement a second recursive function rebuild(node).
    • This function traverses the tree and constructs the final version.
    • For each node, it checks the map. If the map indicates the node is insufficient (sufficientMap.get(node) is false), it returns null, effectively pruning this node and its entire subtree.
    • If the node is sufficient, it recursively calls rebuild for its children: node.left = rebuild(node.left) and node.right = rebuild(node.right).
    • The final result is the tree returned by rebuild(root).

Walkthrough

In this method, we first need to determine for every single node whether it's part of a sufficient path. A node is sufficient if at least one root-to-leaf path passing through it has a sum greater than or equal to limit. We can use a post-order traversal to compute this for all nodes and store the results in a hash map.

Once we have this information, we perform a second traversal (e.g., pre-order) to build the new tree. During this traversal, if we encounter a node that our map indicates is insufficient, we prune it by returning null to its parent. Otherwise, we keep the node and continue the process for its children.

import java.util.HashMap;import java.util.Map; class Solution {    private Map<TreeNode, Boolean> sufficientMap = new HashMap<>();    private int limit;     public TreeNode sufficientSubset(TreeNode root, int limit) {        this.limit = limit;        if (root == null) {            return null;        }                // Pass 1: Populate the map with sufficiency information for each node.        isNodeSufficient(root, 0);                // Pass 2: Rebuild the tree by pruning insufficient nodes.        return rebuild(root);    }     // Pass 1: Returns true if the subtree at 'node' contains a sufficient path.    private boolean isNodeSufficient(TreeNode node, long sum) {        if (node == null) {            return false;        }         sum += node.val;                if (node.left == null && node.right == null) { // Leaf node            boolean sufficient = sum >= limit;            sufficientMap.put(node, sufficient);            return sufficient;        }         boolean leftSufficient = isNodeSufficient(node.left, sum);        boolean rightSufficient = isNodeSufficient(node.right, sum);                // A node is on a sufficient path if any of its descendant paths are sufficient.        boolean isSufficient = leftSufficient || rightSufficient;        sufficientMap.put(node, isSufficient);        return isSufficient;    }     // Pass 2: Returns the modified tree node, or null if it should be pruned.    private TreeNode rebuild(TreeNode node) {        if (node == null) {            return null;        }                // If a node is not on any sufficient path, prune it.        if (!sufficientMap.getOrDefault(node, false)) {            return null;        }                node.left = rebuild(node.left);        node.right = rebuild(node.right);                return node;    }}

Complexity

Time

O(N), where N is the number of nodes. The first pass visits each node once, and the second pass also visits each node once, leading to a total time complexity of O(N) + O(N) = O(N).

Space

O(N), where N is the number of nodes in the tree. This is because we use a hash map to store the sufficiency status for every node.

Trade-offs

Pros

  • The logic is separated into two distinct, clear steps: identification and modification, which can be easier to reason about.

Cons

  • Requires O(N) extra space for the hash map, making it less space-efficient than the single-pass approach.

  • Involves two separate traversals of the tree, which is less elegant and slightly more complex to implement.

Solutions

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode sufficientSubset ( TreeNode root , int limit ) { 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 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem