Insufficient Nodes in Root to Leaf Paths

• 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).

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.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    private Map<TreeNode, Boolean> sufficientMap = new HashMap<>();6    private int limit;7 8    public TreeNode sufficientSubset(TreeNode root, int limit) {9        this.limit = limit;10        if (root == null) {11            return null;12        }13        14        // Pass 1: Populate the map with sufficiency information for each node.15        isNodeSufficient(root, 0);16        17        // Pass 2: Rebuild the tree by pruning insufficient nodes.18        return rebuild(root);19    }20 21    // Pass 1: Returns true if the subtree at 'node' contains a sufficient path.22    private boolean isNodeSufficient(TreeNode node, long sum) {23        if (node == null) {24            return false;25        }26 27        sum += node.val;28        29        if (node.left == null && node.right == null) { // Leaf node30            boolean sufficient = sum >= limit;31            sufficientMap.put(node, sufficient);32            return sufficient;33        }34 35        boolean leftSufficient = isNodeSufficient(node.left, sum);36        boolean rightSufficient = isNodeSufficient(node.right, sum);37        38        // A node is on a sufficient path if any of its descendant paths are sufficient.39        boolean isSufficient = leftSufficient || rightSufficient;40        sufficientMap.put(node, isSufficient);41        return isSufficient;42    }43 44    // Pass 2: Returns the modified tree node, or null if it should be pruned.45    private TreeNode rebuild(TreeNode node) {46        if (node == null) {47            return null;48        }49        50        // If a node is not on any sufficient path, prune it.51        if (!sufficientMap.getOrDefault(node, false)) {52            return null;53        }54        55        node.left = rebuild(node.left);56        node.right = rebuild(node.right);57        58        return node;59    }60}

• Define a single recursive helper function, e.g., isSufficient(node, sum, limit), that returns a boolean.
• This function will perform a post-order traversal. For a given node, it first makes recursive calls for its left and right children.
• The sum parameter tracks the sum of node values from the root to the parent of the current node.
• Base Case: If node is a leaf (node.left == null && node.right == null), the function checks if the total path sum (sum + node.val) is >= limit. It returns true if sufficient, false otherwise.
• Recursive Step: For an internal node:
  • Recursively call isSufficient for the left child: leftSufficient = isSufficient(node.left, sum + node.val, limit). Handle the case where node.left is null (which should result in false).
  • Recursively call isSufficient for the right child: rightSufficient = isSufficient(node.right, sum + node.val, limit).
  • After the recursive calls return, use their boolean results to prune the tree. If leftSufficient is false, set node.left = null. If rightSufficient is false, set node.right = null.
  • The function then returns leftSufficient || rightSufficient. This boolean indicates to the parent caller whether the current node remains part of a sufficient path after potential pruning of its children.
• In the main function, call isSufficient(root, 0, limit). If this initial call returns false, it means the root itself is insufficient, so the entire tree is deleted. In this case, return null. Otherwise, return the modified root.

We can determine if a node is insufficient and prune it in a single pass. The key idea is that a node's sufficiency depends on its children. This suggests a post-order traversal approach.

We define a recursive helper function that takes a node and the sum of the path from the root to its parent. This function will do two things: prune the children if they are roots of insufficient subtrees, and return a boolean indicating if the current node is part of any sufficient path.

For any node, we first recurse on its children. The boolean returned from the recursive calls tells us if a sufficient path exists through the left or right child. If a child's recursive call returns false, it means all paths through that child are insufficient, so we can prune that child by setting the parent's link to null. After handling the children, the current node is sufficient if at least one of its children was on a sufficient path. The base case is a leaf node, where we simply check if its root-to-leaf path sum meets the limit.

1class Solution {2    public TreeNode sufficientSubset(TreeNode root, int limit) {3        // The helper function returns false if the entire tree starting from root is insufficient.4        if (!isSufficient(root, 0, limit)) {5            return null;6        }7        return root;8    }9 10    /**11     * Performs post-order traversal to prune insufficient nodes.12     * @param node The current node.13     * @param sum The sum of values from the root to the parent of `node`.14     * @param limit The threshold.15     * @return true if `node` is part of a sufficient path, false otherwise.16     */17    private boolean isSufficient(TreeNode node, long sum, int limit) {18        if (node == null) {19            return false;20        }21 22        // If it's a leaf node, check if the path sum is sufficient. This is the base case.23        if (node.left == null && node.right == null) {24            return (sum + node.val) >= limit;25        }26 27        // Recursively check left and right subtrees. The sum for the children's path28        // includes the current node's value.29        boolean leftIsSufficient = isSufficient(node.left, sum + node.val, limit);30        boolean rightIsSufficient = isSufficient(node.right, sum + node.val, limit);31 32        // If the left subtree does not have any sufficient path, prune it.33        if (!leftIsSufficient) {34            node.left = null;35        }36 37        // If the right subtree does not have any sufficient path, prune it.38        if (!rightIsSufficient) {39            node.right = null;40        }41 42        // The current node is part of a sufficient path if either of its subtrees43        // (after pruning) contains a sufficient path.44        return leftIsSufficient || rightIsSufficient;45    }46}