Delete Nodes And Return Forest: Splitting a Tree with Post-Order DFS

You are given the root of a binary tree and a list of node values to delete. When you delete a node, its children (if any) become roots of new trees in the resulting forest. Return all the roots of the trees in the forest.

This is LeetCode 1110: Delete Nodes And Return Forest. The trick is that deletion does not just remove a node. It can also promote children into independent trees. You need to handle both actions in a single pass through the tree.

Why this problem matters

Delete Nodes And Return Forest combines two important tree concepts: recursive tree modification and tracking structural changes. You are not just removing nodes. You are producing a collection of trees as output. That means your traversal needs to both prune the tree and collect new roots at the same time.

This pattern of "process a node and decide what to report upward" shows up across many tree problems. If you have solved Binary Tree Pruning, you already know that returning None from a recursive call is a signal to the parent to disconnect a subtree. Delete Nodes And Return Forest extends that idea: when you disconnect a node, you also need to think about what happens to its orphaned children.

The problem also teaches you a useful technique for managing state during tree recursion. Instead of using global flags or extra passes, you can pass an is_root boolean down through the DFS. This tells each node whether it should add itself to the forest if it survives deletion. It is a clean way to avoid adding every single node to the result.

The approach

The key insight is to process nodes bottom-up (post-order). That way, by the time you decide whether to delete a node, its children are already fully processed. Here is the plan:

1. Convert to_delete into a set for O(1) lookups.
2. Run a DFS. At each node, pass down a boolean is_root that says whether this node would be a root of a new tree.
3. A node is a root if its parent was deleted (or if it is the original root).
4. If the current node is not in the delete set and is_root is true, add it to the forest.
5. Recursively process left and right children. Pass root_deleted (whether the current node is being deleted) as the is_root argument, because if the current node is deleted, its children become roots.
6. If the current node is in the delete set, return None to sever it from the parent. Otherwise, return the node.

The solution

def delNodes(root, to_delete):
    to_delete_set = set(to_delete)
    forest = []

    def dfs(node, is_root):
        if not node:
            return None
        root_deleted = node.val in to_delete_set
        if is_root and not root_deleted:
            forest.append(node)
        node.left = dfs(node.left, root_deleted)
        node.right = dfs(node.right, root_deleted)
        return None if root_deleted else node

    dfs(root, True)
    return forest

Let's walk through each piece:

• to_delete_set = set(to_delete) converts the list to a set. This gives you O(1) membership checks instead of O(k) for each node, where k is the number of deletions.
• dfs(node, is_root) takes a node and a boolean. The boolean tracks whether this node should register as a forest root if it survives.
• root_deleted = node.val in to_delete_set checks whether the current node will be removed.
• if is_root and not root_deleted: forest.append(node) adds surviving root nodes to the result. A node is a root if its parent was deleted (or it is the original root) and it is not being deleted itself.
• node.left = dfs(node.left, root_deleted) recurses into the left child. If the current node is being deleted, the left child becomes a potential new root, so we pass root_deleted as the new is_root.
• return None if root_deleted else node severs the node from the tree if it was deleted. The parent will assign None to its left or right pointer, effectively disconnecting the deleted node.

Visual walkthrough

Let's trace the DFS through the tree [1, 2, 3, 4, 5, 6, 7] with to_delete = [3, 5]. The DFS processes children before parents, so we visit nodes in the order 4, 5, 2, 6, 7, 3, 1.

The important moment is Step 6, where node 3 is deleted. Because node 3 is being removed, its children (6 and 7) are told "you are a root now" via the is_root parameter. They each get added to the forest. Then node 3 returns None to node 1, which disconnects the entire right subtree.

Complexity analysis

Time is O(n). Every node is visited exactly once. At each node you do O(1) work: a hash set lookup, a possible append, and two recursive calls (counted separately).

Space is O(n). The hash set takes O(k) space where k is the size of to_delete. The recursion stack takes O(h) where h is the tree height. The result list holds at most O(n) nodes. In total, O(n) dominates.

The building blocks

This problem is built on two fundamental building blocks:

1. Post-order tree transformation (post-order-transform). When you need to modify a tree based on subtree properties, process children first, then decide what to do with the parent. The skeleton:

def transform(node, context):
    if node is None:
        return None
    node.left = transform(node.left, new_context)
    node.right = transform(node.right, new_context)
    if SHOULD_REMOVE(node):
        return None
    return node

For Delete Nodes And Return Forest, SHOULD_REMOVE is node.val in to_delete_set, and new_context is the root_deleted flag. This same skeleton works for any problem where you need to conditionally remove or modify nodes based on their values.

2. Hash set membership (hash-set-lookup). Converting the delete list into a set gives you O(1) lookups. Without this, you would check each node against every value in to_delete, turning an O(n) algorithm into O(n * k). The pattern is simple: whenever you need repeated membership tests against a fixed collection, convert it to a set first.

Edge cases to watch for

• Empty tree (root is None): return an empty list. The DFS base case handles this since it never appends anything.
• Root is in to_delete: the root is removed. Its children (if any) become new forest roots. The initial is_root=True call combined with the deletion check ensures the root is not added to the forest.
• No deletions (to_delete is empty): the original tree is the only item in the forest. Since is_root=True and the root is not deleted, it gets added. No other node has is_root=True.
• Delete all nodes: the forest is empty. Every node is in the delete set, so no node ever passes the is_root and not root_deleted check.
• Delete a leaf node: no children to promote. The leaf just returns None to its parent, which disconnects it. No new roots are created from that deletion.

From understanding to recall

You just walked through a solution that uses post-order DFS with an is_root flag to split a tree into a forest. You saw how deleting a node promotes its children to forest roots, and how the hash set gives you efficient lookups during the traversal.

But will you remember, under pressure, to pass root_deleted as the is_root argument to the children? Will you remember that you need to add the node to the forest before recursing into children, not after? Or will you accidentally add deleted nodes to the forest because you mixed up the condition?

Understanding is not recall. You understood the solution. Recall means you can write it cold, from memory, correctly handling the is_root propagation and the None return for deleted nodes.

Spaced repetition builds recall. You practice writing the solution from scratch at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the DFS with its two parameters, the hash set conversion, and the conditional forest append from memory. After a few repetitions, the post-order-transform pattern and the hash-set-lookup pattern are automatic.

These two building blocks are part of roughly 60 reusable patterns that cover hundreds of LeetCode problems. Drilling them individually is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Binary Tree Pruning - Another post-order tree transformation where you remove subtrees based on a condition. The same "return None to prune" pattern, applied to zero-only subtrees.
• Binary Tree Cameras - Bottom-up tree processing where each node's state depends on its children. Shows how post-order DFS lets you propagate decisions upward.
• Flatten Binary Tree to Linked List - Tree restructuring where you modify pointers during traversal. Another case where recursive return values control how the tree is rewired.