Insufficient Nodes in Root to Leaf Paths

medium binary tree dfs recursion

Problem

Given the root of a binary tree and an integer limit, delete every "insufficient" node. A node is insufficient if every root-to-leaf path that passes through it has a sum strictly less than limit. Return the root of the resulting tree (the root itself may be deleted).

Inputroot = [1,2,3,4,-99,-99,7], limit = 1

Output[1,2,3,4,null,null,7]

Path 1→2→-99 sums to -96 < 1, so the -99 leaf is pruned; the same happens to the other -99 leaf. All remaining paths reach the limit.

tree (level-order, use x for null)

limit

def sufficientSubset(root, limit):
    if not root:
        return None
    if not root.left and not root.right:
        return None if root.val < limit else root
    root.left = sufficientSubset(root.left, limit - root.val)
    root.right = sufficientSubset(root.right, limit - root.val)
    if not root.left and not root.right:
        return None
    return root

function sufficientSubset(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);
  if (!root.left && !root.right) return null;
  return root;
}

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);
        if (root.left == null && root.right == null) return null;
        return root;
    }
}

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);
    if (!root->left && !root->right) return nullptr;
    return root;
}

Explanation

A node should be deleted when every root-to-leaf path through it falls short of limit. The clean way to decide this is a post-order DFS that lets the leaves report back up whether they survive.

The trick is to shrink the limit as we descend. When we move from a node into a child, we subtract the node's value, passing limit - root.val down. That way, by the time we reach a leaf, the remaining limit is exactly what that leaf alone must cover, and we keep it only if root.val >= limit.

After recursing, we reassign root.left and root.right to whatever the calls returned, which may be None if a whole subtree was pruned. A non-leaf node deletes itself precisely when both children ended up gone, because that means no surviving path passes through it.

Example: root = [1,2,3,4,-99,-99,7], limit = 1. Going left, the path 1 → 2 → -99 needs the leaf to be at least 1 - 1 - 2 = -2; -99 < -2, so that leaf is pruned. The same happens to the other -99. Their parents keep a surviving child (4 and 7), so they stay.

Each node is visited once, so this runs in O(n) time with recursion depth equal to the tree height.

Time: O(n) Space: O(h)