Delete Nodes And Return Forest - Leetcode Solution

Problem Statement:

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:

Input: root = [1,2,3,4,5,6,7] to_delete = [3,5] Output: [[1,2,null,4],[6],[7]]

Solution:

To solve this problem, we need to perform the following steps:

1. Create a set of all the values to be deleted.

2. Create an empty list of roots and add the root to it.

3. Iterate through the roots list, for each node, check whether its left and right children are deleted or not. If yes, then remove them and add their child nodes to the roots list.

4. If the current node is deleted, then remove it from its parent node and add its child nodes to the roots list.

5. Return the resultant roots list.

Time Complexity:

The time complexity of the solution is O(n), where n is the total number of nodes in the given binary tree.

Space Complexity:

The space complexity of the solution is O(n), where n is the total number of nodes in the given binary tree.

Code:

Here is the Python solution for the problem:

class Solution:
    def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
        to_delete_set = set(to_delete)
        forest_roots = []

        def dfs(node, parent_exists):
            if not node:
                return None

            if node.val in to_delete_set:
                dfs(node.left, False)
                dfs(node.right, False)
                return None

            if not parent_exists:
                forest_roots.append(node)

            node.left = dfs(node.left, True)
            node.right = dfs(node.right, True)

            return node

        dfs(root, False)

        return forest_roots

1