Delete Nodes Return Forest LeetCode 1110

LeetCode 1110 Delete Nodes and Return Forest gives you a binary tree root and an array of node values to delete. Your task is to perform all deletions and return a list of the roots of the remaining trees — the forest that results after removing every target node.

The problem has two intertwined concerns: actually removing the nodes from the tree structure, and identifying which nodes become new roots in the resulting forest. A node becomes a root either because it was the original root (and was not deleted) or because its parent was deleted and it was not deleted itself.

The constraints allow up to 1000 nodes with values from 1 to 1000. Each node value is unique, which means the to_delete array maps one-to-one to at most one node per value.

The core insight is to use post-order DFS: process the left child, then the right child, then the current node. This bottom-up order is essential because you must know what happens to a node's children before you decide what to do with the node itself.

When a node is deleted, its non-null children become new roots. When a node is not deleted but its parent was deleted, the node becomes a new root. The post-order traversal naturally handles both cases: by the time you process a parent, you have already handled all descendants.

The return value of the recursive function is used to reattach surviving children or sever the edge to deleted nodes. Returning null from a deleted node tells the parent to set that child pointer to null — cleanly detaching the subtree without any explicit parent pointer manipulation.

The recursive function dfs(node, isRoot) takes the current node and a boolean indicating whether the current node should be treated as a potential new root. The isRoot flag is true when the node's parent was deleted (or when it's the original root), signaling that if this node is not deleted it must be added to the result list.

Inside the function: if node is null, return null immediately. Determine whether this node is in the delete set. If isRoot is true and the node is not deleted, add it to the result list — it is a legitimate forest root. Then recurse into children, passing deleted as the isRoot flag for each child.

After recursing, set node.left and node.right to the values returned by the recursive calls. Finally, return null if this node was deleted (severing the edge for the parent) or return node itself if it survives (allowing the parent to keep its child pointer intact).

The isRoot flag is the bridge between deletion and root promotion. When you delete a node, its children do not automatically know they are now roots — the deletion happens at the parent level. Passing isRoot=true when recursing into a deleted node's children propagates that context downward.

Without the isRoot flag you would need a separate pass to find nodes whose parents were deleted, doubling the work. With it, every node receives exactly the context it needs to decide whether to add itself to the result list — all within a single DFS traversal.

The original root is handled uniformly by calling dfs(root, isRoot=True). If root is not deleted it adds itself to the result. If root is deleted, its children receive isRoot=True and the same logic applies recursively down the tree.

Consider the binary tree [1,2,3,4,5,6,7] with toDelete=[3,5]. The tree has root 1, left child 2, right child 3. Node 2's children are 4 and 5. Node 3's children are 6 and 7.

Post-order traversal visits: 4, 5, 2, 6, 7, 3, 1. At node 5: it is in toDelete, so return null — node 2's right pointer becomes null. At node 2: not deleted, isRoot=false (parent 1 is not deleted), so not added to result. At node 3: it is in toDelete, return null — node 1's right pointer becomes null. Nodes 6 and 7, processed before node 3, receive isRoot=true (parent 3 is deleted) and are added to the result.

Final result: the surviving roots are node 1 (original root, not deleted), node 6 (parent 3 deleted), and node 7 (parent 3 deleted). The tree rooted at node 1 now looks like [1,2,null,4] with node 2 having only left child 4.

Python: convert to_delete to a set for O(1) lookup. Define dfs(node, is_root). Inside: if not node return None. deleted = node.val in to_delete_set. if is_root and not deleted: result.append(node). node.left = dfs(node.left, deleted). node.right = dfs(node.right, deleted). return None if deleted else node. Call dfs(root, True) and return result. Time O(n), space O(n) for the set plus the recursion stack depth O(h).

Java: use a HashSet<Integer> for the delete set. The recursive method returns TreeNode (null for deleted nodes). For each child call: node.left = dfs(node.left, deleted, toDeleteSet, result). The isRoot parameter is a boolean. Add node to result list when isRoot && !deleted. Java's call stack handles recursion up to the default limit; for very deep trees consider an iterative BFS approach with a queue tracking (node, isRoot) pairs.

Both solutions have O(n) time complexity — each node is visited exactly once. Space is O(n) for the hash set and O(h) for the recursion stack where h is the tree height. For a balanced tree h = O(log n); for a skewed tree h = O(n). The result list holds at most n nodes in the pathological case where every non-deleted node is a new root.

Delete Node in a BST (LeetCode 450) tackles single-node deletion in a binary search tree, requiring careful rebalancing by finding the in-order successor or predecessor. Unlike 1110 which deletes multiple nodes in an unordered tree, 450 must maintain BST ordering invariants throughout the deletion.

Flatten Binary Tree to Linked List (LeetCode 114) restructures the tree in place using a post-order or Morris traversal — the same post-order intuition applies. Serialize and Deserialize Binary Tree (LeetCode 297) requires traversal to encode tree structure, again leveraging DFS patterns shared with this problem.

The broader tree transformation family includes problems where you modify tree structure during traversal: Prune Binary Tree (LeetCode 814), which removes subtrees containing only zeros, uses the same return-null-to-sever pattern. Any problem asking you to conditionally remove nodes and reconnect survivors is a candidate for this post-order DFS with null-return technique.