Given the root of a binary tree, each node in the tree has a distinct value.
After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).
Return the roots of the trees in the remaining forest. You may return the result in any order.
Example 1:
Input: root = [1,2,3,4,5,6,7], to_delete = [3,5] Output: [[1,2,null,4],[6],[7]]
Example 2:
Input: root = [1,2,4,null,3], to_delete = [3] Output: [[1,2,4]]
Constraints:
1000.1 and 1000.to_delete.length <= 1000to_delete contains distinct values between 1 and 1000.Problem Overview: Given a binary tree and a list of node values to delete, remove those nodes and return the roots of the remaining trees (the forest). When a node is deleted, its non-deleted children become new roots in the resulting forest.
Approach 1: Post-order Traversal (O(n) time, O(h) space)
This approach uses Depth-First Search with a post-order traversal. You process the left and right children before the current node, which ensures you already know whether a child was deleted before deciding how to handle the parent. Store all values from to_delete in a hash table for O(1) lookup. During recursion, if the current node must be deleted, push its non-null children into the forest list and return null to detach it from its parent. If the node stays, return it normally. The root requires special handling: if it is not deleted, add it to the forest at the start. This method touches each node exactly once, giving O(n) time and O(h) recursion stack space where h is the tree height.
The key insight is that deletions affect parent-child links. Post-order traversal lets you resolve children first, so by the time you evaluate a node you already know whether its subtrees survived or were removed. This prevents dangling references and keeps the logic compact.
Approach 2: BFS with Parent References (O(n) time, O(n) space)
This approach performs a level-order traversal using a queue on the Binary Tree. Along with each node, track its parent and whether it is a left or right child. Again, keep a hash set of nodes to delete for constant-time checks. When visiting a node marked for deletion, detach it from its parent and push its children into the forest if those children are not also scheduled for deletion. Continue BFS until every node is processed.
This strategy works well when you prefer iterative traversal instead of recursion. Because the queue may hold many nodes at once, the auxiliary memory can reach O(n) in the worst case. The logic is slightly more verbose because you explicitly update parent pointers during deletion, but the algorithm still processes each node only once.
Recommended for interviews: The post-order DFS approach is what interviewers usually expect. It shows clear understanding of tree traversal order and how structural modifications propagate upward in recursion. BFS with parent references is also valid, but the DFS solution is shorter, easier to reason about, and demonstrates stronger control over recursive tree manipulation.
This approach uses a tree traversal technique, specifically post-order traversal, to manage the deletion process. By performing the traversal from the leaves to the root, you can easily detach the nodes that need to be deleted. Each subtree that gets detached as a result of deleting a node potentially becomes a representative of a new tree in the forest.
The solution uses a nested function helper that recursively traverses the tree in a post-order fashion. Inside the helper, it checks if the current node should be deleted. If it's a root node of a new tree and not deleted, it is added to the result list. Each child node is checked in a similar manner, ensuring that disconnected subtrees form new roots if they're not in the delete set.
Python
JavaScript
Time Complexity: O(N), as each node is visited once.
Space Complexity: O(N), accounting for the implicit space used by the recursive stack.
This approach involves using a breadth-first search (BFS) paradigm that keeps track of each node's parent. When we encounter a node that is to be deleted, we modify the parent's pointer to null, effectively removing the node. At the same time, if this deleted node has children, they become new tree roots if they are not included in the deletion list.
The Java solution uses a queue to traverse the tree in a level-order manner. For each node processed, it checks if the node's children need deletion. If so, it ensures the respective children are handled (either added to the result as new roots or their pointers reset). The traversal ensures all deletions are effectively managed within a single pass through the tree.
Time Complexity: O(N), as all nodes are processed individually.
Space Complexity: O(N), since the queue can hold at most all nodes plus necessary supporting storage like HashSet.
First, we use a hash table or an array of length 1001, s, to record all nodes that need to be deleted.
Next, we design a function dfs(root) that returns the root of the subtree with root as the root after deleting all nodes that need to be deleted. The execution logic of the function dfs(root) is as follows:
root is null, we return null;dfs(root.left) and dfs(root.right), and assign the return values to root.left and root.right respectively. If root does not need to be deleted, we return root; if root needs to be deleted, we check whether root.left and root.right are null. If they are not null, we add them to the answer array; finally, we return null.In the main function, we call dfs(root). If the result is not null, it means that the root node does not need to be deleted, and we add the root node to the answer array. Finally, we return the answer array.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the tree.
Python
Java
C++
Go
TypeScript
JavaScript
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Post-order Traversal | Time Complexity: O(N), as each node is visited once. |
| Approach 2: BFS with Parent References | Time Complexity: O(N), as all nodes are processed individually. |
| DFS | — |
| BFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Post-order Traversal (DFS) | O(n) | O(h) | Best general solution for tree deletion problems. Preferred in interviews due to clean recursion and minimal extra memory. |
| BFS with Parent References | O(n) | O(n) | Useful when avoiding recursion or when implementing iterative tree traversal with explicit parent tracking. |
Delete Nodes and Return Forest • Kevin Naughton Jr. • 31,446 views views
Watch 9 more video solutions →Practice Delete Nodes And Return Forest with our built-in code editor and test cases.
Practice on FleetCode