# 1273. Delete Tree Nodes

A tree rooted at node 0 is given as follows:

The number of nodes is nodes; The value of the i-th node is value[i]; The parent of the i-th node is parent[i]. Remove every subtree whose sum of values of nodes is zero.

After doing so, return the number of nodes remaining in the tree.

Example 1:

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2

# Solution

Approach 1: DFS after reconstructing the tree.

Approach 2: assuming the params are given top down (numbering the nodes from root to leaf in level order), can go through the array without reconstructing the tree.

# Code (Python)

Approach 1:

import collections
class Solution:
    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:
        if not nodes:
            return 0
        children = collections.defaultdict(list)
        for i, val in enumerate(parent):
            children[val].append(i)
        root = children.pop(-1)[0]
        return self._recurse(root, children, value)[1]
    
    def _recurse(self, node, children, value):
        # return (sum, num of undeleted nodes in subtree including self)
        total = value[node]
        count = 1
        for child in children[node]:
            child_total, child_count = self._recurse(child, children, value)
            total += child_total
            count += child_count
        if total == 0:
            return (0, 0)
        return (total, count)

Approach 2:

    def deleteTreeNodes(self, n: int, parent: List[int], value: List[int]) -> int:
        # Without reconstructing the tree. This assumes the params are given top down (numbering the nodes from root to leaf in level order)
        if n == 1:
            return 0 if value[0] == 0 else 1
        res = [1] * n
        for i in range(n - 1, 0, -1):
            value[parent[i]] += value[i]
            res[parent[i]] += res[i] if value[i] else 0
        return res[0]

# Code (C++)

Approach 1:

Approach 2: