Delete Nodes And Return Forest

Delete Nodes And Return Forest

1. What is this problem about?

The Delete Nodes And Return Forest interview question asks you to take a binary tree and a list of values to delete. After removing the specified nodes, the tree breaks into several disjoint subtrees (a "forest"). You need to return a list of the roots of these new trees. This Delete Nodes And Return Forest coding problem requires managing connectivity while traversing the hierarchy.

2. Why is this asked in interviews?

Companies like Microsoft and Pinterest ask this to evaluate your mastery of Binary Tree interview patterns and recursive state management. It requires you to track whether a node's parent was deleted, which determines if the current node becomes a new root in the resulting forest.

3. Algorithmic pattern used

The most effective pattern is Post-order Traversal (DFS) with a Hash Set for $O(1)$ deletion lookups.

• Traverse the tree bottom-up.
• For each node, check if it should be deleted.
• If it's deleted, its children (if they aren't also deleted) become roots of new trees.
• If a node is NOT deleted but its parent WAS, the current node becomes a new root.

4. Example explanation

Tree: 1 is root, children 2, 3. Nodes to delete: [2].

1. Visit 2. It's in the delete list.
2. If 2 had children (say 4, 5), they would be added to the forest result list.
3. The parent 1 sets its left child to null.
4. Since 1 was the original root and wasn't deleted, the result is [root(1), root(4), root(5)].

5. Common mistakes candidates make

• Top-down errors: Using pre-order traversal can make it difficult to "sever" the connection from the parent to the deleted child.
• Duplicate Roots: Accidentally adding the original root to the forest when it is also in the to_delete list.
• Set usage: Using a list for the deletion check ($O(N)$) instead of a set ($O(1)$), leading to poor performance.

6. Interview preparation tip

Practice returning "state" from recursive calls. In this problem, the recursive function often returns the node itself (or null if deleted) to the caller, which allows the parent to easily update its child pointers. This "return and update" technique is vital for tree-pruning tasks.