1273. Delete Tree Nodes

MediumTreeDepth-First SearchBreadth-First Search

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.

Flowchart Walkthrough

Let's analyze Leetcode 1273. Delete Tree Nodes using the provided flowchart. We'll explore each node step-by-step to determine the appropriate algorithm:

Is it a graph?

Yes: The problem involves nodes and can be visualized as a tree, which is a specific type of graph.

Is it a tree?

Yes: The nodes and parent references specify a tree structure.

Conclusion: According to the flowchart, after confirming it's a tree, we move to use DFS. Trees inherently benefit from Depth-First Search for navigation and manipulation, especially where parent-child relationships are vital, as in this deletion problem. Thus, DFS is appropriate for efficiently solving this problem.

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:

Create graph g where each node keeps a list of its children.
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.
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.
Return the sum and count of nodes from this subtree.
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:

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:
```
g = defaultdict(list)
for i in range(1, nodes):
    g[parent[i]].append(i)
```
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.
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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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:

     0(1)
    /   \
  1(-2) 3(4)
  / |
2(-3) 4(3)
|
5(-3)

The numbers in parentheses are the node values.

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

0: [1, 3]
1: [2, 4, 5]

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

1from typing import List
2from collections import defaultdict
3
4class Solution:
5    def deleteTreeNodes(self, nodes: int, parents: List[int], values: List[int]) -> int:
6        # Helper function to perform Depth-First Search (DFS)
7        def dfs(node_index):
8            # Initialize the sum of subtree values and count of nodes as the node's own value and 1, respectively.
9            subtree_sum, node_count = values[node_index], 1
10          
11            # Recur for all children of the current node.
12            for child_index in graph[node_index]:
13                child_sum, child_count = dfs(child_index)
14                subtree_sum += child_sum
15                node_count += child_count
16          
17            # If the total sum of the subtree including the current node is zero,
18            # the entire subtree is deleted, so set the node count to zero.
19            if subtree_sum == 0:
20                node_count = 0
21          
22            # Return tuple of subtree sum and number of nodes after deletions (if any).
23            return (subtree_sum, node_count)
24
25        # Generating the graph from the parent array, representing the tree structure.
26        graph = defaultdict(list)
27        for i in range(1, nodes):
28            graph[parents[i]].append(i)
29      
30        # Starting DFS from the root node (node index 0) and returning the count of remaining nodes.
31        return dfs(0)[1]
32
33# Example usage:
34# sol = Solution()
35# print(sol.deleteTreeNodes(nodes=7, parents=[-1,0,0,1,2,2,2], values=[1,-2,4,0,-2,-1,-1]))
36# The above call would return 2, as two nodes remain after deleting nodes with a subtree sum of 0.
37

1class Solution {
2    private List<Integer>[] graph; // Adjacency list to represent the tree
3    private int[] nodeValues; // Values corresponding to each node
4
5    // Computes the number of nodes remaining after deleting nodes with a subtree sum of zero
6    public int deleteTreeNodes(int nodes, int[] parent, int[] value) {
7        // Initialize graph representation of nodes
8        graph = new List[nodes];
9        for (int i = 0; i < nodes; i++) {
10            graph[i] = new ArrayList<>();
11        }
12        // Build the tree structure in the adjacency list format
13        for (int i = 1; i < nodes; i++) {
14            graph[parent[i]].add(i); // Add child to parent's list
15        }
16        // Assign node values
17        this.nodeValues = value;
18        // Perform depth-first search and determine the result
19        return dfs(0)[1]; // The second value in the returned array is the count of remaining nodes
20    }
21
22    // Performs a depth-first search and returns an array with subtree sum and number of nodes
23    private int[] dfs(int nodeIndex) {
24        // Initialize with the current node's value and count (1)
25        int[] result = new int[]{nodeValues[nodeIndex], 1};
26        // Process all the children of the current node
27        for (int childIndex : graph[nodeIndex]) {
28            int[] subtreeResult = dfs(childIndex);
29            // Add child's values to current sum and count
30            result[0] += subtreeResult[0];
31            result[1] += subtreeResult[1];
32        }
33        // If the subtree sum equals 0, the entire subtree is deleted
34        if (result[0] == 0) {
35            result[1] = 0; // Set the count to 0 because the subtree will be deleted
36        }
37        return result; // Return the sum and count of the subtree rooted at the current node
38    }
39}
40

1class Solution {
2public:
3    int deleteTreeNodes(int totalNodes, vector<int>& parent, vector<int>& value) {
4        // Build the graph as an adjacency list where each node points to its children
5        vector<vector<int>> graph(totalNodes);
6        for (int i = 1; i < totalNodes; ++i) {
7            graph[parent[i]].emplace_back(i);
8        }
9      
10        // Recursive depth-first search function that returns the sum of values and count of nodes in a subtree
11        // including the root of that subtree
12        function<pair<int, int>(int)> depthFirstSearch = [&](int node) -> pair<int, int> {
13            int sum = value[node]; // Start with the value of current node
14            int count = 1; // Count of nodes starts at 1 for the current node
15            // Iterate over the children of the current node
16            for (int child : graph[node]) {
17                auto [childSum, childCount] = depthFirstSearch(child); // Recursively get sum and count of child subtree
18                sum += childSum; // Add child subtree sum to current sum
19                count += childCount; // Add child subtree count to current count
20            }
21            // If the sum of the subtree including the current node is 0, discard the subtree
22            if (sum == 0) {
23                count = 0;
24            }
25            return pair<int, int>{sum, count}; // Return the resulting sum and count of the subtree
26        };
27      
28        // Start the DFS at the root node (0) and return the count of the remaining nodes in the tree
29        return depthFirstSearch(0).second;
30    }
31};
32

1type TreeNode = { sum: number; count: number };
2
3// The input arrays represent the parents and the respective value of each tree node
4let totalNodes: number;
5let parent: number[];
6let value: number[];
7
8// The adjacency list will represent the graph where each node points to its children
9let graph: number[][] = [];
10
11// Function to build the graph as an adjacency list
12function buildGraph(): void {
13    graph = Array.from({ length: totalNodes }, () => []);
14    for (let i = 1; i < totalNodes; ++i) {
15        graph[parent[i]].push(i);
16    }
17}
18
19// Recursive depth-first search to calculate the sum of node values in the subtree and count of nodes
20function depthFirstSearch(node: number): TreeNode {
21    let sum: number = value[node]; // Initialize sum with the value of the current node
22    let count: number = 1; // Initialize count as 1 for the current node
23
24    // Process all children of the current node
25    for (let child of graph[node]) {
26        let { sum: childSum, count: childCount } = depthFirstSearch(child); // Recursive call
27        sum += childSum; // Increment the sum by the child's subtree sum
28        count += childCount; // Increment count by the child's subtree count
29    }
30
31    // If the subtree sum is zero, the entire subtree is discarded
32    if (sum === 0) count = 0;
33
34    return { sum, count }; // Return the sum and count of the subtree
35}
36
37// Main function to delete tree nodes based on the given rules
38function deleteTreeNodes(totalNodes: number, parent: number[], value: number[]): number {
39    // Initialize variables with provided inputs
40    this.totalNodes = totalNodes;
41    this.parent = parent;
42    this.value = value;
43
44    buildGraph(); // Construct the graph from input arrays
45
46    // Start DFS from the root node (0) and return the count of remaining nodes after deletions
47    return depthFirstSearch(0).count;
48}
49

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:

The code performs a single depth-first search (DFS) traversal of the tree.
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.
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).