1273. Delete Tree Nodes

Problem Description

This problem presents us with a tree where each node contains a specific value. The tree is rooted at node 0, and consists of nodes number of nodes. Each node i has a value value[i] and a parent node indexed by parent[i]. The task is to remove all subtrees which have a total sum of node values equal to zero. A subtree here is defined as a node, all its descendants, and all the connections between them. The objective is to determine the count of nodes remaining in the tree after all such zero-sum subtrees are removed.

Intuition

The intuition behind the solution comes from a postorder depth-first search (DFS) traversal of the tree. In postorder traversal, we visit a node's children before the node itself. This gives us a way to calculate the sum of the subtree rooted at each node, starting from the leaves up to the root.

The core idea is to:

1. Create graph g where each node keeps a list of its children.
2. Perform a DFS starting from the root node (indexed as 0) and recursively call DFS on its children to calculate the total sum of the subtree rooted at that node as well as the number of nodes in this subtree.
3. During the DFS, when we calculate the sum of the values in a subtree, if the sum is zero, we set the count of nodes in that subtree to zero, effectively removing it.
4. Return the sum and count of nodes from this subtree.
5. Upon completion of DFS, the result from the root node will give us the number of remaining nodes after all the zero-sum subtrees have been removed.

This approach capitalizes on the fact that a zero-sum subtree higher in the tree will include any zero-sum subtrees within it, meaning we will correctly "remove" those zero-sum subtrees in the process.

Learn more about Tree, Depth-First Search and Breadth-First Search patterns.

Solution Approach

The implementation of the solution approach involves two main parts: building a representation of the tree and performing a depth-first search to process and remove zero-sum subtrees.

The following data structures and algorithms are used:

• A defaultdict of lists to represent the graph (g). This is used to store the tree structure where each key is a node and the values are the list of its children.
• A recursive depth-first search (dfs) function that takes a node index (i) as an argument and returns a tuple containing the sum of values of the subtree rooted at that node and the number of remaining nodes in that subtree.

Here is a step-by-step breakdown of how the implementation works:

1. Graph construction: We iterate through the parent list starting from the first node (ignoring the root node at index 0, since it does not have a parent) and create an adjacency list representation of the tree. For each child node, it is appended to the list of its parent node in the graph. This is done by the code snippet:

   1g = defaultdict(list)
   2for i in range(1, nodes):
   3    g[parent[i]].append(i)

2. Postorder DFS traversal: The dfs function works recursively and is called for the root node to start the process. It performs postorder traversal:

   • Initially, for each node, we assign s to its own value and set m (the node count) to 1.
   • The function then iterates over all children of the current node, stored in g, and calls dfs for each child node.
   • The sum of values s and the count m are updated with the results from children nodes. This is where the sum of the subtree is accumulated.
   • If the sum of the subtree up to this point is zero (s == 0), we set m to 0, effectively discarding this subtree.
   • The function returns a tuple (s, m), representing the sum and the count of nodes in the current subtree.

3. Cleaning and final result: After the dfs(0) is called, it cascades up the recursion stack and sums up child nodes, checking for sums of zero. It uses the return value of m to determine if the subtree should be discarded. The final number of nodes of the whole tree is returned using dfs(0)[1] which is the second element of the tuple indicating the count of nodes remaining.

The entire function and postorder DFS ensure we remove all zero-sum subtrees and count the number of nodes left effectively. After running this algorithm, we get the answer to our problem—how many nodes are remaining in the tree after zero-sum subtrees are removed.

Example Walkthrough

Let's use a small example to illustrate the solution approach. Suppose the input is such that nodes = 6, the values array that represents each node's value is [1, -2, -3, 4, 3, -3], and the parent array that tells us each node's parent is [-1, 0, 1, 0, 1, 1]. This means the tree structure is the following:

1     0(1)
2    /   \
3  1(-2) 3(4)
4  / |
52(-3) 4(3)
6|
75(-3)

The numbers in parentheses are the node values.

1. Graph construction: Based on the parent array, our graph g will be:

   10: [1, 3]
   21: [2, 4, 5]

2. Postorder DFS traversal:
   • When the dfs is called on node 0, it will then call dfs on its children 1 and 3.
   • The dfs(3) call will immediately return (4, 1) because node 3 has no children.
   • dfs(1) on the other hand calls dfs on nodes 2, 4, and 5.
   • dfs(2) returns (-3, 1), dfs(4) returns (3, 1), and dfs(5) returns (-3, 1).
   • dfs(1) accumulates the values and counts coming from its children (-3 + 3 + -3 = -3) and its own value to find the sum is -2 - 3 = -5, which is not zero. Thus, it returns (-5, 4) because it has 3 children plus itself, but the subtree at node 1 is not a zero-sum subtree.
   • Back to dfs(0), we combine the results from its children 1 and 3. The sum is 1 + 4 + -5 = 0 and the count would normally be 6. However, since this subtree sums to zero, we now set the count to 0.

So, as per the dfs on node 0, the entire tree sums to zero, meaning all nodes would be removed. Hence, the final result would be 0, since the zero-sum subtree in this case is the entire tree itself.

The output for our example would be that there are 0 nodes remaining after removing zero-sum subtrees. This is because eliminating the zero-sum subtree rooted at node 0 (the entire tree) leaves us with no nodes.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(N), where N is the number of nodes in the tree.

The reasoning for this complexity is as follows:

1. The code performs a single depth-first search (DFS) traversal of the tree.
2. During the traversal, for each node, it aggregates the sum of values (s) and counts the number of nodes (m) in its subtree including itself, unless the subtree sum is zero, in which case the count is set to zero.
3. Each node is visited exactly once during the DFS, and the work done at each node is proportional to the number of its children, which, across all nodes, sums to N - 1 (total edges in a tree with N nodes).

Therefore, the entire operation is linear with respect to the number of nodes.

Space Complexity

The space complexity of the given code is O(N).

The reasoning for this complexity is as follows:

1. The g variable is a dictionary representation of the tree, and in the worst case, it might need to store N lists (one for each node). Each list might contain a separate child, and therefore, the total space taken up by g is proportional to N.
2. The recursion stack during the DFS traversal will, in the worst case, go as deep as the height of the tree. In the worst case of a skewed tree, where the tree takes the form of a list, the height could also be N.
3. No other significant space-consuming structures or variables are used.

Combining the space requirements for the dictionary and the recursion stack gives us a combined space complexity of O(N).

Learn more about how to find time and space complexity quickly using problem constraints.