Delete Nodes And Return Forest

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. For example:

If root = [1,2,3,4,5,6,7] and to_delete = [3,5], the expected output is [[1,2,null,4],[6],[7]] If root = [1,2,4,null,3] and to_delete = [3], the expected output is [[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 and contains distinct values between 1 and 1000.

# 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: TreeNode, to_delete: list[int]) -> list[TreeNode]:
        """
        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.
        """
        result = []
        to_delete_set = set(to_delete)

        def helper(node: TreeNode, is_root: bool) -> TreeNode:
            if not node:
                return None

            if node.val in to_delete_set:
                node.left = helper(node.left, True)
                node.right = helper(node.right, True)
                return None

            else:
                if is_root:
                    result.append(node)

                node.left = helper(node.left, False)
                node.right = helper(node.right, False)
                return node

        helper(root, True)
        return result

Explanation:

1. Data Structures:

   • TreeNode: Definition of a binary tree node with val, left, and right attributes.

2. Algorithm:

   • The delNodes function takes the root of the binary tree and a list of node values to delete as input.
   • It initializes an empty list result to store the roots of the remaining forest.
   • It converts the to_delete list into a set to_delete_set for faster lookups.
   • It defines a recursive helper function helper that takes a node and a boolean is_root as input.
     • If the node is None, it returns None.
     • If the node's value is in to_delete_set:
       • It recursively calls helper on the left and right children, setting is_root to True because the children will be roots of new trees.
       • It returns None to remove the current node from the tree.
     • Otherwise:
       • If is_root is True, it means the current node is the root of a tree, so it adds it to the result list.
       • It recursively calls helper on the left and right children, setting is_root to False because they are no longer roots.
       • It returns the current node.
   • It calls the helper function on the root node with is_root set to True.
   • It returns the result list.

Example:

Consider the following binary tree:

      1
     / \
    2   3
   / \ / \
  4  5 6  7

And to_delete = [3, 5]

1. The delNodes function is called with the root 1 and to_delete = [3, 5].
2. to_delete_set = {3, 5}.
3. The helper function is called with node 1 and is_root = True.
4. Since 1 is not in to_delete_set, 1 is added to result.
5. helper is called on 2 with is_root = False.
6. Since 2 is not in to_delete_set, helper is called on 4 with is_root = False.
7. Since 4 is not in to_delete_set, helper is called on None with is_root = False.
8. helper is called on 5 with is_root = False.
9. Since 5 is in to_delete_set, helper is called on None with is_root = True and returns None.
10. helper is called on None with is_root = True and returns None.
11. 5 is removed from the tree.
12. helper is called on 3 with is_root = False.
13. Since 3 is in to_delete_set, helper is called on 6 with is_root = True. 6 is added to result.
14. helper is called on None with is_root = False.
15. helper is called on 7 with is_root = True. 7 is added to result.
16. helper is called on None with is_root = False.
17. 3 is removed from the tree.
18. The function returns [1, 6, 7].

Big O Run-time Analysis:

• The helper function visits each node in the tree once, so the time complexity is O(N), where N is the number of nodes in the tree.
• The to_delete list is converted into a set for faster lookups, which takes O(K) time, where K is the length of the to_delete list. However, this is dominated by the O(N) time complexity of the helper function.
• Therefore, the overall time complexity is O(N).

Big O Space Usage Analysis:

• The to_delete_set takes O(K) space, where K is the length of the to_delete list.
• The result list takes O(M) space, where M is the number of trees in the remaining forest. In the worst case, M can be equal to N, so the space complexity can be O(N).
• The recursion stack of the helper function can take O(H) space, where H is the height of the tree. In the worst case, the tree can be skewed, so H can be equal to N, and the space complexity can be O(N).
• Therefore, the overall space complexity is O(N).

Edge Cases:

• If the root is None, the function should return an empty list.
• If to_delete is empty, the function should return the original tree.
• If all nodes are in to_delete, the function should return an empty list.
• If the tree is skewed, the recursion stack can take O(N) space.

Handling Edge Cases:

• The code handles the case where the root is None by returning an empty list.
• The code handles the case where to_delete is empty by not deleting any nodes.
• The code handles the case where all nodes are in to_delete by returning an empty list.
• The code handles the case where the tree is skewed by using recursion, which can take O(N) space in the worst case.