Delete Nodes And Return Forest - Video Solutions

Problem Overview: Given a binary tree and a list of node values to delete, remove those nodes and return the roots of the remaining trees (the forest). When a node is deleted, its non-deleted children become new roots in the resulting forest.

Approach 1: Post-order Traversal (O(n) time, O(h) space)

This approach uses Depth-First Search with a post-order traversal. You process the left and right children before the current node, which ensures you already know whether a child was deleted before deciding how to handle the parent. Store all values from to_delete in a hash table for O(1) lookup. During recursion, if the current node must be deleted, push its non-null children into the forest list and return null to detach it from its parent. If the node stays, return it normally. The root requires special handling: if it is not deleted, add it to the forest at the start. This method touches each node exactly once, giving O(n) time and O(h) recursion stack space where h is the tree height.

The key insight is that deletions affect parent-child links. Post-order traversal lets you resolve children first, so by the time you evaluate a node you already know whether its subtrees survived or were removed. This prevents dangling references and keeps the logic compact.

Approach 2: BFS with Parent References (O(n) time, O(n) space)

This approach performs a level-order traversal using a queue on the Binary Tree. Along with each node, track its parent and whether it is a left or right child. Again, keep a hash set of nodes to delete for constant-time checks. When visiting a node marked for deletion, detach it from its parent and push its children into the forest if those children are not also scheduled for deletion. Continue BFS until every node is processed.

This strategy works well when you prefer iterative traversal instead of recursion. Because the queue may hold many nodes at once, the auxiliary memory can reach O(n) in the worst case. The logic is slightly more verbose because you explicitly update parent pointers during deletion, but the algorithm still processes each node only once.

Recommended for interviews: The post-order DFS approach is what interviewers usually expect. It shows clear understanding of tree traversal order and how structural modifications propagate upward in recursion. BFS with parent references is also valid, but the DFS solution is shorter, easier to reason about, and demonstrates stronger control over recursive tree manipulation.