Delete Tree Nodes

Delete Tree Nodes

1. What is this problem about?

The Delete Tree Nodes interview question presents a tree where each node has an associated integer value. Your task is to delete every subtree whose total sum of node values equals zero. After these deletions, you need to return the count of nodes remaining in the tree. This Delete Tree Nodes coding problem requires calculating aggregate properties from the bottom up.

2. Why is this asked in interviews?

Microsoft uses this question to test Depth-First Search interview patterns and tree representation skills. Often, the tree is given as an array of parents rather than a standard node structure. It evaluates your ability to build an adjacency list and perform post-order calculations to determine subtree sums.

3. Algorithmic pattern used

This problem follows the Post-order DFS (Bottom-Up) pattern.

• You need to know the sum of a node's children before you can calculate the node's own total subtree sum.
• The recursive function should return two values: the sum of the subtree and the count of non-deleted nodes in that subtree.
• If the sum at a node is 0, the count returned to its parent is 0 (effectively deleting the subtree).

4. Example explanation

Suppose you have a root 0 (value 1) with child 1 (value -1).

1. Go to child 1. Its subtree sum is -1.
2. Return to root 0. Total sum = $1 + (-1) = 0$.
3. Since the total sum at the root is 0, the entire tree is deleted. Result: 0 nodes.

5. Common mistakes candidates make

• Top-down approach: Attempting to delete nodes before knowing the total sum of their descendants.
• Building the tree incorrectly: Failing to convert the "parent array" input into an efficient adjacency list for traversal.
• Global state issues: Using global variables for counts that get messed up during recursion.

6. Interview preparation tip

Practice returning tuples or small objects from recursive functions. In tree problems, you often need multiple pieces of information (like sum, height, and node count) simultaneously to make a decision at the parent level.