Delete Nodes And Return Forest
Last Updated: April 3, 2026
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.
So the problem boils down to two things happening simultaneously: 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 interesting part is that deletion and root-collection are intertwined. You can't just delete everything first and then figure out the roots, because deleting a node is what creates new roots (its children). You need to handle both in a single pass through the tree.
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
The most straightforward way to think about this: traverse the tree, find every node that needs deleting, and handle the consequences. For each deleted node, we need to disconnect it from its parent and promote its children to new roots.
A BFS (level-order traversal) lets us process nodes one by one. We maintain a parent map so that when we delete a node, we can go back to its parent and set the appropriate child pointer to null. After processing all deletions, we collect the remaining roots.
This approach is conceptually simple but requires bookkeeping: a parent map, a set of deleted nodes, and careful handling of the root node as a special case.
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.
This approach works correctly but requires two full tree traversals and an extra parent map. What if we processed children before parents so we could handle deletions and pointer updates in a single pass?
Approach 2: Post-Order DFS (Optimal)
Intuition
The key insight is that if we process children before their parent (post-order traversal), we can handle everything in one clean pass. When we visit a node, its children have already been processed, so we know their final state. If the current node needs to be deleted, its surviving children are already fully processed and can be added as new roots. We return null to the parent to sever the link.
There's one more thing to track: whether a node is a potential root. A node is a root if its parent was deleted (or if it's the original root). So we pass an isRoot flag down the recursion. If a node is a root and it's not being deleted, we add it to the forest.
This gives us a single DFS that simultaneously deletes nodes, promotes children, and collects roots.
The elegance of this approach comes from how it combines three operations into one recursive pass. First, it decides whether each node is a new root by checking the isRoot flag (which is true when the parent was deleted or for the original root). Second, it severs parent-child links by returning null when a node is deleted. Third, it propagates the "your parent was deleted" information downward through the shouldDelete flag becoming the child's isRoot flag.
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(n). The HashSet stores at most d values (d <= n). The recursion stack can go as deep as the tree's height, which is O(n) in the worst case (a skewed tree) and O(log n) for a balanced tree.