# Delete Nodes And Return Forest
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/delete-nodes-and-return-forest)
Canonical: https://scaleengineer.com/dsa/problems/delete-nodes-and-return-forest
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, Hash Table, Tree, Binary Tree
---
## Problem
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:**

![](https://assets.glich.co/dsa/delete-nodes-and-return-forest/image0.png) 

**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 `1` and `1000`.
* `to_delete.length <= 1000`
* `to_delete` contains distinct values between `1` and `1000`.

# Approaches
## Multi-Pass Approach with Parent Pointers
This approach tackles the problem by first building auxiliary data structures to represent the tree's relationships, specifically mapping each node to its parent. It involves three main phases: first, a traversal to build the parent map; second, iterating through the nodes to be deleted and using the map to sever their connections to their parents; and third, another pass to identify and collect the roots of the remaining disconnected trees.
**Time:** O(N + M), where N is the number of nodes and M is the length of `to_delete`. Populating the maps takes O(N). Creating the `to_delete` set takes O(M). The deletion and root-finding steps each take O(M) and O(N) respectively. The dominant factor is the linear scan, resulting in O(N + M). · **Space:** O(N + M), where N is the number of nodes and M is the length of `to_delete`. The `parentMap` and `valToNodeMap` each store N entries, requiring O(N) space. The `toDeleteSet` requires O(M) space. The queue for BFS can take up to O(N) space in the worst case.
**Pros:** The logic is broken down into clear, distinct steps: mapping, deleting, and collecting roots.; It avoids recursion, which can prevent stack overflow issues on extremely deep trees (though not an issue with the given constraints).
**Cons:** Requires multiple passes over the tree or data structures derived from it.; Uses significant extra space, O(N), for the parent and value-to-node maps, which can be substantial for large trees.; The implementation is more complex and less intuitive than a single-pass recursive solution.
### Explanation
This method breaks down the problem into more manageable, sequential steps. 

1.  **Build Parent and Value Maps:** We begin by traversing the entire tree, typically with a queue for a BFS traversal. During the traversal, we populate two maps: a `parentMap` (`Map<TreeNode, TreeNode>`) that stores the parent of each node, and a `valToNodeMap` (`Map<Integer, TreeNode>`) that allows us to quickly access any `TreeNode` given its value. 

2.  **Perform Deletions:** After mapping the tree structure, we iterate through the `to_delete` array. For each value, we find the `nodeToDelete` using `valToNodeMap`. We then find its `parentNode` using `parentMap`. If a parent exists, we determine if `nodeToDelete` is a left or right child and set the corresponding pointer on the `parentNode` to `null`, effectively disconnecting it.

3.  **Identify Forest Roots:** The final step is to find the roots of the forest. A node becomes a root if it hasn't been deleted, but its parent has. We iterate through all the nodes of the original tree. For each node, we check if its value is in the `to_delete` set. If it's not, we check its parent using `parentMap`. If the node has no parent (it's the original root) or its parent's value is in the `to_delete` set, we add the node to our result list, `forest`.

```java
class Solution {
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        if (root == null) {
            return new ArrayList<>();
        }

        Map<TreeNode, TreeNode> parentMap = new HashMap<>();
        Map<Integer, TreeNode> valToNodeMap = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);
        valToNodeMap.put(root.val, root);
        parentMap.put(root, null);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                parentMap.put(node.left, node);
                valToNodeMap.put(node.left.val, node.left);
                queue.offer(node.left);
            }
            if (node.right != null) {
                parentMap.put(node.right, node);
                valToNodeMap.put(node.right.val, node.right);
                queue.offer(node.right);
            }
        }

        Set<Integer> toDeleteSet = new HashSet<>();
        for (int val : to_delete) {
            toDeleteSet.add(val);
        }

        for (int valToDelete : to_delete) {
            TreeNode nodeToDelete = valToNodeMap.get(valToDelete);
            if (nodeToDelete == null) continue;

            TreeNode parent = parentMap.get(nodeToDelete);
            if (parent != null) {
                if (parent.left == nodeToDelete) {
                    parent.left = null;
                } else if (parent.right == nodeToDelete) {
                    parent.right = null;
                }
            }
        }

        List<TreeNode> forest = new ArrayList<>();
        for (TreeNode node : valToNodeMap.values()) {
            if (!toDeleteSet.contains(node.val)) {
                TreeNode parent = parentMap.get(node);
                if (parent == null || toDeleteSet.contains(parent.val)) {
                    forest.add(node);
                }
            }
        }

        return forest;
    }
}
```
### Algorithm
- Create a `Map<TreeNode, TreeNode> parentMap` to store the parent of each node and a `Map<Integer, TreeNode> valToNodeMap` to find a node by its value.
- Traverse the tree using Breadth-First Search (BFS) or Depth-First Search (DFS) to populate both maps.
- Convert the `to_delete` array into a `HashSet<Integer>` for efficient O(1) average time lookups.
- Iterate through each value in the `to_delete` set. For each value, find the corresponding node and its parent using the maps. Disconnect the node from its parent by setting the parent's `left` or `right` child pointer to `null`.
- Initialize an empty list `forest` to store the roots of the resulting trees.
- Iterate through all nodes in the original tree (e.g., using `valToNodeMap.values()`).
- For each node, if it is not marked for deletion, check if its parent was deleted (or if it was the original root). A node is a new root if it is not in the `to_delete` set, but its parent is (or it has no parent).
- Add all such identified root nodes to the `forest` list.
- Return the `forest` list.

## Single-Pass Post-Order Traversal (DFS)
This approach uses a single-pass Depth-First Search (DFS) to solve the problem efficiently. By using a post-order traversal, we can process a node's children before the node itself. This allows us to decide whether to keep or discard a node based on the already processed subtrees. A helper function recursively traverses the tree, returning the modified subtree root to its caller. This enables a parent to update its child pointers correctly. New roots for the forest are identified and collected during this single traversal.
**Time:** O(N + M), where N is the number of nodes and M is the length of `to_delete`. We visit each node exactly once, performing constant time operations (including the O(1) hash set lookup). Creating the set takes O(M). Thus, the total time is linear in the size of the input. · **Space:** O(N + M), where N is the number of nodes and M is the length of `to_delete`. The recursion stack depth can be up to the height of the tree, O(H), which is O(N) in the worst-case (a skewed tree). The `toDeleteSet` requires O(M) space, and the `forest` list can store up to O(N) roots.
**Pros:** Extremely efficient as it processes the entire tree in a single pass.; The code is concise and elegant, leveraging recursion to naturally handle the tree structure.; Modifies the tree in-place, which is memory-efficient for the tree data itself.
**Cons:** The recursive approach can lead to a `StackOverflowError` if the tree is extremely deep, although this is not a concern with the given constraint of N <= 1000.; The logic, while elegant, can be slightly harder to grasp initially compared to a step-by-step iterative approach.
### Explanation
The key to this efficient solution is a post-order traversal, which ensures that when we visit a node, we have already processed its entire left and right subtrees. We define a recursive helper function, `helper(node, isRoot)`, which returns the `TreeNode` that should be the new child for its parent, or `null` if the link should be severed.

First, we convert the `to_delete` array into a `HashSet` for fast lookups. We also initialize our result list, `forest`.

The `helper(node, isRoot)` function works as follows:
1.  **Base Case:** If `node` is `null`, we return `null`.
2.  **Check for Deletion:** We determine if the current `node`'s value is in our `toDeleteSet`. Let's call this boolean `deleted`.
3.  **Post-order Recursion:** We recursively call `helper` on the children. A child becomes a potential new root (`isRoot = true`) if its parent (the current node) is being deleted. So we call `node.left = helper(node.left, deleted)` and `node.right = helper(node.right, deleted)`.
4.  **Identify New Roots:** A node is added to the `forest` if it's a potential root (`isRoot` is true) AND it is not being deleted (`!deleted`). This condition correctly identifies the start of a new tree.
5.  **Return Value:** The function returns `null` if the current node is being deleted (`deleted` is true), which tells the parent to remove its reference to this node. Otherwise, it returns the `node` itself.

The initial call is `helper(root, true)`, signifying that the original root is a potential root of a tree in the final forest.

```java
class Solution {
    private Set<Integer> toDeleteSet;
    private List<TreeNode> forest;

    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        toDeleteSet = new HashSet<>();
        for (int val : to_delete) {
            toDeleteSet.add(val);
        }
        forest = new ArrayList<>();

        helper(root, true);

        return forest;
    }

    private TreeNode helper(TreeNode node, boolean isRoot) {
        if (node == null) {
            return null;
        }

        boolean deleted = toDeleteSet.contains(node.val);
        
        if (isRoot && !deleted) {
            forest.add(node);
        }

        // A child becomes a root candidate if its parent is deleted.
        node.left = helper(node.left, deleted);
        node.right = helper(node.right, deleted);

        // Return null if the current node is to be deleted.
        return deleted ? null : node;
    }
}
```
### Algorithm
- Convert the `to_delete` array into a `HashSet` for efficient O(1) average time lookups.
- Initialize an empty `List<TreeNode>` to store the roots of the forest.
- Define a recursive helper function that performs a post-order traversal of the tree. This function will take a node and a boolean flag `isRoot` as input.
- In the helper function, first, recursively call it for the left and right children. The key is to pass a new `isRoot` flag to these calls: if the current node is to be deleted, its children become potential new roots.
- After the recursive calls return, the links to the children (`node.left` and `node.right`) are updated with the results.
- Now, process the current node. If the `isRoot` flag is true for this node and it is *not* in the `to_delete` set, it's a root of a tree in the forest, so add it to the result list.
- Finally, the helper function returns `null` if the current node is in the `to_delete` set (effectively deleting it from its parent's perspective), otherwise, it returns the node itself.
- Start the process by calling the helper function on the original root with `isRoot` set to `true`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private boolean [] s = new boolean [ 1001 ]; private List < TreeNode > ans = new ArrayList <>(); public List < TreeNode > delNodes ( TreeNode root , int [] to_delete ) { for ( int x : to_delete ) { s [ x ] = true ; } if ( dfs ( root ) != null ) { ans . add ( root ); } return ans ; } private TreeNode dfs ( TreeNode root ) { if ( root == null ) { return null ; } root . left = dfs ( root . left ); root . right = dfs ( root . right ); if (! s [ root . val ]) { return root ; } if ( root . left != null ) { ans . add ( root . left ); } if ( root . right != null ) { ans . add ( root . right ); } return null ; } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number[]} to_delete * @return {TreeNode[]} */ var delNodes =
  function (root, to_delete) {
    const s = Array(1001).fill(false);
    for (const x of to_delete) {
      s[x] = true;
    }
    const ans = [];
    const dfs = (root) => {
      if (!root) {
        return null;
      }
      root.left = dfs(root.left);
      root.right = dfs(root.right);
      if (!s[root.val]) {
        return root;
      }
      if (root.left) {
        ans.push(root.left);
      }
      if (root.right) {
        ans.push(root.right);
      }
      return null;
    };
    if (dfs(root)) {
      ans.push(root);
    }
    return ans;
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < TreeNode *> delNodes ( TreeNode * root , vector < int >& to_delete ) { bool s [ 1001 ]; memset ( s , 0 , sizeof ( s )); for ( int x : to_delete ) { s [ x ] = true ; } vector < TreeNode *> ans ; function < TreeNode * ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) -> TreeNode * { if ( ! root ) { return nullptr ; } root -> left = dfs ( root -> left ); root -> right = dfs ( root -> right ); if ( ! s [ root -> val ]) { return root ; } if ( root -> left ) { ans . push_back ( root -> left ); } if ( root -> right ) { ans . push_back ( root -> right ); } return nullptr ; }; if ( dfs ( root )) { ans . push_back ( root ); } return ans ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def delNodes ( self , root : Optional [ TreeNode ], to_delete : List [ int ] ) -> List [ TreeNode ]: def dfs ( root : Optional [ TreeNode ]) -> Optional [ TreeNode ]: if root is None : return None root . left , root . right = dfs ( root . left ), dfs ( root . right ) if root . val not in s : return root if root . left : ans . append ( root . left ) if root . right : ans . append ( root . right ) return None s = set ( to_delete ) ans = [] if dfs ( root ): ans . append ( root ) return ans
```