DSA problem
Delete Nodes And Return Forest
Given the root of a binary tree, each node in the tree has a distinct value. After deleting all nodes whose values are in to_delete, the remaining forest is the set of disjoint trees. Return the roots of the trees in the remaining forest in any order.
The trick is to perform a post-order traversal. When we visit a node, we recursively process its children first; each recursive call returns either the (possibly trimmed) subtree rooted at that child, or null if the child itself was deleted. Only after both children have been resolved do we decide what to do with the current node.
If the current node's value is in to_delete, its surviving children become new roots of the forest (we add any non-null child to the result), and we return null to our parent so the parent's pointer to us is severed. If the current node is not to be deleted, we return it unchanged so the parent keeps the link.
There is one boundary case worth highlighting: the original root might be deleted, in which case any of its surviving subtrees that were not added inside the recursion must still be included in the answer. A clean way to handle this is to seed the result with the root if it survives — equivalently, treat the root's parent as a virtual deleted node so the same rule applies uniformly. The whole algorithm runs in O(n + d) time, where d = |to_delete|, using a hash set for O(1) deletion lookups and O(h) recursion space.
Examples
root = [1,2,3,4,5,6,7], to_delete = [3,5][[1,2,null,4],[6],[7]]root = [1,2,4,null,3], to_delete = [3][[1,2,4]]root = [1,2,3], to_delete = [1][[2],[3]]Constraints
- The number of nodes in the tree is in the range [1, 1000].
- Each node has a distinct value between 1 and 1000.
- 1 <= to_delete.length <= 1000
- Each value in to_delete is in the range [1, 1000] and is distinct.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.