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.
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 setm
(the node count) to 1. - The function then iterates over all children of the current node, stored in
g
, and callsdfs
for each child node. - The sum of values
s
and the countm
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 setm
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.
- Initially, for each node, we assign
-
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 ofm
to determine if the subtree should be discarded. The final number of nodes of the whole tree is returned usingdfs(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 EvaluatorExample 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 graphg
will be:0: [1, 3] 1: [2, 4, 5]
- Postorder DFS traversal:
- When the
dfs
is called on node 0, it will then calldfs
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 callsdfs
on nodes 2, 4, and 5.dfs(2)
returns(-3, 1)
,dfs(4)
returns(3, 1)
, anddfs(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 children1
and3
. The sum is1 + 4 + -5 = 0
and the count would normally be 6. However, since this subtree sums to zero, we now set the count to0
.
- When the
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 withN
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:
- The
g
variable is a dictionary representation of the tree, and in the worst case, it might need to storeN
lists (one for each node). Each list might contain a separate child, and therefore, the total space taken up byg
is proportional toN
. - 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
. - 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.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Want a Structured Path to Master System Design Too? Donāt Miss This!