Delete Nodes And Return Forest
Understanding the Problem
We have a binary tree and a list of node values to delete. When we delete a node, it disappears from the tree, and its children (if any) become roots of new independent trees. The original root is also a tree in the forest, unless it gets deleted too.
The problem combines two tasks: removing nodes and collecting the roots of the resulting subtrees. A node becomes a new root when its parent gets deleted (or when it was the original root and it survives). A node stops being a root if it itself gets deleted.
The two tasks are coupled. Deleting a node is what creates new roots (its children), so deletion and root collection have to be tracked together during the traversal rather than handled in separate phases.
Key Constraints:
Number of nodes <= 1000-> The tree is small. Even O(n^2) runs instantly. The focus is on getting the logic right, not on performance.Each node has a distinct value between 1 and 1000-> Distinct values mean we can use a HashSet for O(1) deletion lookups. No ambiguity about which node to delete.to_delete.length <= 1000-> The delete list can be as large as the tree itself (we might delete every node). We need to handle the case where nothing survives.
Approach 1: BFS with Parent Tracking
Intuition
Traverse the tree, find every node that needs deleting, and handle the consequences at each one: disconnect it from its parent and promote its surviving children to new roots.
A BFS (level-order traversal) processes nodes one by one, but it reaches a node without remembering who its parent was, and the disconnect happens at the parent. So we first build a parent map, then run a second BFS that performs the deletions. Each node decides its own fate independently: if a deleted node's child is also marked for deletion, the child is not promoted here; its own surviving children get promoted when the BFS reaches that child.
The bookkeeping adds up: a parent map, a set of values to delete, and the original root handled as a special case at the end.
Algorithm
- Build a parent map by traversing the tree, storing each node's parent.
- Put all values to delete into a HashSet for O(1) lookup.
- Use BFS to traverse the tree. For each node that needs to be deleted:
- If it has a parent, set the parent's left or right child to null (whichever points to this node).
- If it has a left child that is not being deleted, add that child to the result list.
- If it has a right child that is not being deleted, add that child to the result list.
- After processing all nodes, if the original root was not deleted, add it to the result list.
- Return the result list.
Example Walkthrough
Code
- Time Complexity: O(n). We traverse the tree twice: once to build the parent map and once to process deletions. Each traversal is O(n). Building the delete set is O(d) where d is the size of
to_delete, and d <= n. - Space Complexity: O(n). The parent map stores one entry per node. The BFS queue holds at most one level of the tree at a time, which is O(n) in the worst case.
The two passes and the parent map exist because BFS reaches a node before its children, so a deleted node has to reach back up to its parent to sever the link. A traversal that resolves children before finalizing the parent's pointers removes both costs, which is the next approach.
Approach 2: Post-Order DFS (Optimal)
Intuition
A recursive DFS can sever links without any parent map by using its return value: each call returns what the parent's pointer should become, the node itself if it survives or null if it is deleted. The parent assigns node.left = dfs(node.left, ...) after the recursive call finishes, so every severed link is updated exactly where it is stored, in the parent. This is the post-order part: a node's child pointers are finalized only after both subtrees have been resolved.
Root status flows in the opposite direction, downward. A node is a root of the forest when its parent was deleted (or when it is the original root), so the current node's "I am being deleted" decision becomes the child's isRoot flag in the recursive call. On entering a node, if isRoot is true and the node survives, it goes into the forest.
One DFS therefore deletes nodes, promotes children, and collects roots, with no parent map and no second traversal.
A surviving root is added to the forest on entry, before its subtree has been cleaned of deleted descendants. This is safe because the forest stores a reference to the node, not a copy. The recursive calls that follow prune deleted descendants in place, so by the time the top-level call returns, every tree reachable from the forest list is in its final shape.
Algorithm
- Put all values from
to_deleteinto a HashSet for O(1) lookup. - Define a recursive DFS function that takes a node and a boolean
isRootflag. - If the node is null, return null.
- Check if the current node needs to be deleted.
- If the node is a root and is not being deleted, add it to the result list.
- Recursively process the left child. If the current node is being deleted, the left child becomes a potential root (pass
isRoot = true). Otherwise passisRoot = false. - Recursively process the right child with the same logic.
- If the current node is being deleted, return null (so the parent severs its link). Otherwise return the node.
- Start the DFS from the root with
isRoot = true.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node exactly once during the DFS. Each visit does O(1) work (a HashSet lookup and a comparison). Building the delete set takes O(d) where d is the length of
to_delete. - Space Complexity: O(h) for the recursion stack, where h is the tree height (O(n) worst case for a skewed tree, O(log n) when balanced), plus O(d) for the HashSet of values to delete, with d <= n.