599/670

599. Delete Nodes And Return Forest

Medium

You are given the root of a binary tree in which every node carries a distinct value, and a list to_delete of values to remove. Removing a node erases it completely: its parent loses that child, and each child the removed node had (left and/or right) becomes the root of its own independent tree. After all removals, the surviving nodes form a forest — a set of disjoint trees.

Your function receives root and the list to_delete (every listed value appears in the tree) and returns the roots of the trees in the resulting forest. You may return the roots in any order — the judge canonicalizes: each tree is printed in preorder, and trees are ordered by where their root sat in a preorder walk of the original tree.

Deleting 3 and 5 from the example treeLeft: the original tree with the doomed nodes 3 and 5 shown dashed. Right: the forest that remains — deleting leaf 5 promotes nothing, while deleting 3 cuts its children 6 and 7 loose as new roots.

Example 1:

Input: root = [1, 2, 3, 4, 5, 6, 7], to_delete = [3, 5]

Output: [[1, 2, 4], [6], [7]] (each tree shown in preorder)

Explanation: Removing 5 (a leaf) just shrinks node 2's subtree. Removing 3 disconnects its children, so 6 and 7 each become the root of a new tree. Three trees remain: the one still rooted at 1, plus 6 and 7.

Example 2:

Input: root = [1, 2, 4, null, 3], to_delete = [3]

Output: [[1, 2, 4]]

Explanation: Node 3 is a leaf, so deleting it promotes nothing — the rest of the tree stays connected as a single tree.

Constraints:

The tree has between 1 and 1000 nodes.
Node values are distinct integers between 1 and 1000.
1 ≤ to_delete.length ≤ 1000
The values in to_delete are distinct and every one of them appears in the tree.

Hints:

A node becomes a root of the forest exactly when it survives but its parent does not (the original root counts as having no parent). Can you compute that with information passed *down* the recursion?

Deleting is easiest bottom-up: fix the children first, then decide this node's fate. If a helper returns the node that should replace it (itself, or nothing), the parent can simply assign `node.left = helper(node.left, ...)`.

Carry a boolean `parent_deleted` down the DFS. If this node survives and `parent_deleted` is true, append it to the answer; if this node is deleted, its children recurse with `parent_deleted = true`.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: root = [1, 2, 3, 4, 5, 6, 7], to_delete = [3, 5]

Expected output: [[1, 2, 4], [6], [7]]