Problem Description

You are given two integer arrays: parent and value. The parent array defines a rooted tree structure with n nodes (indexed from 0 to n-1). Specifically, parent[i] is the parent of node i; the root node has parent[i] == -1. Each node i has an integer value value[i].

Your task is to delete every subtree whose sum of all its nodes' values is zero. After all such deletions, return the number of nodes remaining in the tree.

• The tree is static and will not change its structure except for the deletions you perform.
• Each subtree includes a node and all its descendants.
• There is only one root node (where parent[i] == -1).
• The solution should not reuse elements or delete a node more than once.

Thought Process

The problem asks us to remove all subtrees whose total sum is zero. At first glance, a brute-force approach might be to compute the sum for every possible subtree, but this would be very inefficient since there are exponentially many subtrees.

However, since the tree is rooted and each node has a unique parent, we can traverse the tree in a post-order manner (process children before parents). This way, we can compute the sum for each subtree efficiently in a single pass: for any node, the sum of its subtree is the sum of its value and the sums of its children's subtrees.

If a node's subtree sum is zero, we mark it (and its entire subtree) for deletion. We only need to keep track of the nodes that remain after all such deletions.

This insight allows us to avoid unnecessary recomputation and leads to an efficient, recursive solution.

Solution Approach

To solve the problem efficiently, we use a post-order traversal (depth-first search) to process the tree from the leaves up to the root:

1. Build the Tree:
   • We first construct a children list for each node using the parent array, so we can easily access all children of a node.
2. Recursive Post-Order Traversal:
   • We define a function that, for each node, recursively computes the sum of its subtree and counts how many nodes remain after deleting any zero-sum subtrees below it.
   • If a node's subtree sum is zero, we delete the whole subtree (i.e., it contributes zero to the remaining node count).
   • Otherwise, we add the current node and the remaining nodes in its children.
3. Return the Result:
   • We start the traversal from the root node and return the total count of remaining nodes.

We use a hash map or list of lists to store the children of each node for O(1) access, which makes the traversal efficient.

Example Walkthrough

Example Input:
parent = [-1, 0, 0, 1, 1, 2, 2]
value = [1, -2, 4, 0, -2, -1, 1]

The tree structure is:

• Node 0 (root): children 1, 2
• Node 1: children 3, 4
• Node 2: children 5, 6
• Nodes 3, 4, 5, 6: leaves

We traverse from the leaves:

• Node 3: value 0 → sum is 0, so delete node 3.
• Node 4: value -2 → sum is -2, keep node 4.
• Node 1: value -2 + (0 from 3) + (-2 from 4) = -4, keep node 1 and its remaining child (4).
• Node 5: value -1 → sum is -1, keep node 5.
• Node 6: value 1 → sum is 1, keep node 6.
• Node 2: value 4 + (-1 from 5) + (1 from 6) = 4, keep node 2 and its children (5, 6).
• Node 0: value 1 + (-4 from 1) + (4 from 2) = 1, keep node 0 and all its remaining children.

Code Implementation

class Solution:
    def deleteTreeNodes(self, n, parent, value):
        from collections import defaultdict
        tree = defaultdict(list)
        root = -1
        for i, p in enumerate(parent):
            if p == -1:
                root = i
            else:
                tree[p].append(i)
        
        def dfs(node):
            total = value[node]
            count = 1
            for child in tree[node]:
                child_sum, child_count = dfs(child)
                total += child_sum
                count += child_count
            if total == 0:
                return (0, 0)
            else:
                return (total, count)
        
        return dfs(root)[1]
      

class Solution {
public:
    int deleteTreeNodes(int n, vector<int>& parent, vector<int>& value) {
        vector<vector<int>> tree(n);
        int root = -1;
        for (int i = 0; i < n; ++i) {
            if (parent[i] == -1) root = i;
            else tree[parent[i]].push_back(i);
        }
        function<pair<int,int>(int)> dfs = [&](int node) {
            int total = value[node];
            int count = 1;
            for (int child : tree[node]) {
                auto [child_sum, child_count] = dfs(child);
                total += child_sum;
                count += child_count;
            }
            if (total == 0) return make_pair(0, 0);
            else return make_pair(total, count);
        };
        return dfs(root).second;
    }
};
      

class Solution {
    public int deleteTreeNodes(int n, int[] parent, int[] value) {
        List<List<Integer>> tree = new ArrayList<>();
        for (int i = 0; i < n; i++) tree.add(new ArrayList<>());
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (parent[i] == -1) root = i;
            else tree.get(parent[i]).add(i);
        }
        int[] res = dfs(root, tree, value);
        return res[1];
    }
    private int[] dfs(int node, List<List<Integer>> tree, int[] value) {
        int total = value[node];
        int count = 1;
        for (int child : tree.get(node)) {
            int[] childRes = dfs(child, tree, value);
            total += childRes[0];
            count += childRes[1];
        }
        if (total == 0) return new int[]{0, 0};
        else return new int[]{total, count};
    }
}
      

var deleteTreeNodes = function(n, parent, value) {
    let tree = Array.from({length: n}, () => []);
    let root = -1;
    for (let i = 0; i < n; i++) {
        if (parent[i] === -1) root = i;
        else tree[parent[i]].push(i);
    }
    function dfs(node) {
        let total = value[node];
        let count = 1;
        for (let child of tree[node]) {
            let [child_sum, child_count] = dfs(child);
            total += child_sum;
            count += child_count;
        }
        if (total === 0) return [0, 0];
        else return [total, count];
    }
    return dfs(root)[1];
};
      

Time and Space Complexity

Brute-force approach: If we tried to compute the sum for every possible subtree, the time complexity would be exponential (O(2^n)), which is infeasible for large trees.

Optimized approach: Our solution visits each node once, and for each node, processes all its children. Thus, the time complexity is O(n), where n is the number of nodes in the tree.
Space complexity: We use O(n) extra space to store the tree structure and for the recursion stack in the worst case (when the tree is a chain).

Summary

The key insight is to use post-order traversal to efficiently compute subtree sums and delete zero-sum subtrees in one pass. By building a child adjacency list and recursively processing each node from the leaves up, we avoid redundant calculations and achieve linear time complexity. This makes the solution both elegant and efficient for large trees.