Maximum Score After Applying Operations on a Tree

medium tree dfs dp

Problem

You are given a tree rooted at node 0 where each node holds a value. In one operation you may pick any node, add its value to your score, and set that node's value to 0. The tree must stay healthy: the sum of values on every path from the root to a leaf must remain greater than 0 — so each root-to-leaf path must keep at least one non-zero node.

Return the maximum score you can collect. Equivalently, the score equals the total of all values minus the minimum amount you are forced to leave behind to keep every path healthy.

Inputvalues = [20,10,9,7,4,3,5] (as a rooted tree)

Output40

Total is 58. Each subtree keeps the cheaper of its own root value or its children's required keep, forcing 18 to stay → score 58 − 18 = 40.

values as level-order tree (use "null" for missing children)

def maximum_score_after_operations(root):
    total = [0]
    def collect(node):
        if node:
            total[0] += node.val
            collect(node.left)
            collect(node.right)
    collect(root)

    def min_keep(node):
        if not node:
            return 0
        if not node.left and not node.right:
            return node.val
        children = min_keep(node.left) + min_keep(node.right)
        return min(node.val, children)

    return total[0] - min_keep(root)

function maximumScoreAfterOperations(root) {
  let total = 0;
  (function collect(node) {
    if (!node) return;
    total += node.val;
    collect(node.left);
    collect(node.right);
  })(root);

  function minKeep(node) {
    if (!node) return 0;
    if (!node.left && !node.right) return node.val;
    const children = minKeep(node.left) + minKeep(node.right);
    return Math.min(node.val, children);
  }

  return total - minKeep(root);
}

class Solution {
    private long total = 0;
    public long maximumScoreAfterOperations(TreeNode root) {
        collect(root);
        return total - minKeep(root);
    }
    private void collect(TreeNode node) {
        if (node == null) return;
        total += node.val;
        collect(node.left);
        collect(node.right);
    }
    private long minKeep(TreeNode node) {
        if (node == null) return 0;
        if (node.left == null && node.right == null) return node.val;
        long children = minKeep(node.left) + minKeep(node.right);
        return Math.min(node.val, children);
    }
}

long long total = 0;
void collect(TreeNode* node) {
    if (!node) return;
    total += node->val;
    collect(node->left);
    collect(node->right);
}
long long minKeep(TreeNode* node) {
    if (!node) return 0;
    if (!node->left && !node->right) return node->val;
    long long children = minKeep(node->left) + minKeep(node->right);
    return min((long long)node->val, children);
}
long long maximumScoreAfterOperations(TreeNode* root) {
    collect(root);
    return total - minKeep(root);
}

Explanation

Maximizing the score is the same as minimizing what we must leave behind. The score is total - kept, where kept is the sum of values we are forced to keep non-zero to keep all paths healthy.

For any subtree, what is the cheapest way to keep all of its root-to-leaf paths healthy? There are two choices. Either we keep this node's value — that single node sits on every path through the subtree, so all of its paths are covered at cost node.val. Or we zero this node and instead pay to keep each child's subtree healthy independently.

So minKeep(node) = min(node.val, minKeep(left) + minKeep(right)). A leaf must keep its own value — there is no node below it to protect the path, so the base case returns node.val.

We sum all values once for total, run the post-order DP to get minKeep(root), and the answer is the difference. Each node is visited a constant number of times, so it is linear.

Example with values [20,10,9,7,4,3,5]: the leaves (7,4,3,5) must be kept on their own paths, but higher up we compare keeping an ancestor versus its children. The DP settles on keeping 18 total, giving score 58 - 18 = 40.

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