Delete Nodes And Return Forest
Problem Description
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:
- The number of nodes in the given tree is at most
1000. - Each node has a distinct value between
1and1000. to_delete.length <= 1000to_deletecontains distinct values between1and1000.
Solve it on LeetCode
Approaches
1. Recursive DFS Approach
Intuition:
The problem requires us to return a forest of trees by deleting certain nodes from a binary tree. We can tackle this problem using a recursive approach. The primary idea is to traverse the tree using DFS (Depth First Search) and make decisions at each node whether it is to be deleted or retained.
- For each node, recursively decide for its left and right children whether they need to be deleted.
- If a node is to be deleted, its children are added to the result list of roots if they are non-null.
- If a node is not deleted, and it is a root (i.e., the start of recursion), add it to the result list of roots.
Steps:
- Start from the root of the tree.
- Use recursion to traverse the tree.
- At each recursive call, check if the current node is in the delete list.
- If it is, add its children to the forest if they exist.
- If not, keep traversing, possibly marking this node to remain as part of an existing tree.
Code:
- Time Complexity: O(n), where (n) is the number of nodes in the tree. Each node is processed once.
- Space Complexity: O(h + d), where (h) is the height of the tree and (d) is the number of nodes to delete (to store in HashSet).
2. Optimized Recursive DFS with Set
Intuition:
This approach enhances the first solution by using a HashSet to store nodes that need to be deleted, making the check for deletions (O(1)) on average. This makes it slightly more optimal for larger sets of nodes to be deleted.
Same steps as above, but the check for deletion is turned into an (O(1)) operation by using a Set data structure.
Code:
- Time Complexity: O(n), as each node is visited only once.
- Space Complexity: O(h + d).
- The O(h) is for the recursion stack (maximum is the height of the binary tree).
- The O(d) is for the set containing nodes to be deleted (if using mutable data structures for large delete lists).