Start by scanning the binary tree and marking nodes to delete in a hash set for constant lookup. Traverse the tree recursively, detaching deleted nodes and adding their non-deleted children to the result forest. This approach guarantees O(n) time while handling each node exactly once and prevents common mistakes like losing child connections during deletion.
Problem Statement
You are given the root of a binary tree where each node has a unique value. Given a list of values to delete, remove all nodes matching any value in the list.
After deletions, multiple disconnected trees may remain. Return the roots of all remaining trees as a list, representing the forest formed by removing the specified nodes. The order of trees in the output does not matter.
Examples
Example 1
Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]
Example details omitted.
Example 2
Input: root = [1,2,4,null,3], to_delete = [3]
Output: [[1,2,4]]
Example details omitted.
Constraints
- The number of nodes in the given tree is at most 1000.
- Each node has a distinct value between 1 and 1000.
- to_delete.length <= 1000
- to_delete contains distinct values between 1 and 1000.
Solution Approach
Hash set for deletion lookup
Store all values to delete in a hash set for O(1) access. This ensures that each node can be checked quickly during traversal, preventing unnecessary repeated scans.
Recursive DFS traversal
Perform a depth-first search from the root. If a node is in the delete set, recursively process its children and add non-deleted ones to the forest. Return null for deleted nodes to disconnect them from their parent.
Forest collection and result formation
Whenever a non-deleted node has no parent (root or child of a deleted node), add it to the forest list. Collecting roots during traversal avoids an extra pass and ensures all trees in the forest are captured.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(n) |
Time complexity is O(n) because each node is visited once. Space complexity is O(n) for the hash set storing nodes to delete and for recursion stack in the worst case of a skewed tree.
What Interviewers Usually Probe
- Asks about handling child nodes of deleted parents.
- Probes if the hash set lookup is necessary for efficiency.
- Questions how to maintain forest roots without extra passes.
Common Pitfalls or Variants
Common pitfalls
- Forgetting to add child nodes of deleted nodes to the forest.
- Modifying the tree incorrectly, losing subtrees during deletion.
- Using repeated linear scans instead of a hash set, causing O(n^2) behavior.
Follow-up variants
- Delete nodes with values in a given range instead of an explicit list.
- Return the forest in a specific order, such as preorder traversal of roots.
- Handle trees where duplicate values may exist, requiring careful identification.
How GhostInterview Helps
- Identifies nodes to delete efficiently using hash sets for quick lookup.
- Guides recursive traversal and ensures proper detachment of deleted nodes.
- Automatically collects forest roots without losing child subtrees.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the most efficient way to track nodes to delete in Delete Nodes And Return Forest?
Use a hash set for all to_delete values to allow constant-time lookup during DFS traversal.
How do I handle child nodes of a deleted parent?
Add each non-deleted child to the forest list when their parent is removed to maintain the correct forest structure.
Can I solve this without recursion?
Yes, iterative DFS or BFS with a stack or queue is possible, but recursion simplifies handling child connections and forest collection.
What is the time complexity of this approach?
O(n) because each node is visited once and each hash set lookup is O(1).
Why is array scanning plus hash lookup important here?
It ensures fast identification of nodes to delete and prevents losing children in the forest, avoiding inefficient repeated tree scans.
Need direct help with Delete Nodes And Return Forest instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Delete Nodes And Return Forest from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the lowest common ancestor of the deepest leaves in a binary tree using efficient traversal and state tracking techniques.
Open problem page#987 Vertical Order Traversal of a Binary TreePerform a vertical order traversal of a binary tree, sorting nodes by their values within columns.
Open problem page#1261 Find Elements in a Contaminated Binary TreeRecover values in a contaminated binary tree and efficiently check for existence using traversal and state tracking techniques.
Open problem page