Delete Tree Nodes - Solution & Explanation

Problem Overview: You are given a tree with n nodes represented by a parent array and a value array. If the sum of values in any subtree becomes zero, that entire subtree must be deleted. The goal is to return the number of nodes remaining after all zero-sum subtrees are removed.

Approach 1: Postorder DFS on Tree (O(n) time, O(n) space)

The key observation: whether a node stays in the tree depends on the total sum of its entire subtree. This naturally leads to a postorder traversal using Depth-First Search. First build an adjacency list from the parent array so you can traverse children efficiently. During DFS, recursively compute the subtree sum and the node count for each child. If a child's subtree sum becomes zero, you discard that subtree by not adding its sum or count to the parent. Otherwise, accumulate both values. After processing all children, if the current subtree sum equals zero, return (0, 0) to signal that the whole subtree should be removed.

This works because postorder traversal ensures children are processed before the parent. Every node is visited exactly once, so the time complexity is O(n) and the recursion stack plus adjacency list uses O(n) space. This is the cleanest and most common solution for problems combining tree traversal with subtree aggregation.

Approach 2: Leaf Processing with Reverse BFS / Topological Order (O(n) time, O(n) space)

Another way to think about the problem is processing the tree from leaves upward. Track the number of children for each node and push all leaves into a queue. Using a strategy similar to Breadth-First Search, process nodes whose children are already handled. Each node contributes its value to its parent unless its accumulated subtree sum becomes zero. If the sum is zero, the subtree is removed and contributes nothing upward. Otherwise, propagate the sum and node count to the parent.

This approach simulates a bottom-up evaluation without recursion. It works well when recursion depth could be large or when you want an iterative solution. The complexity remains O(n) time since each node is processed once, with O(n) space for queues and auxiliary arrays.

Recommended for interviews: The postorder DFS approach is what most interviewers expect. It directly models the "compute subtree result before parent" pattern that appears frequently in tree problems. Starting with a DFS solution demonstrates strong understanding of subtree aggregation. Mentioning the bottom-up BFS/topological variant shows deeper insight into alternative tree processing strategies.