Code Implementation

# 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, to_delete):
        to_delete_set = set(to_delete)
        forest = []

        def helper(node, is_root):
            if not node:
                return None
            root_deleted = node.val in to_delete_set
            if is_root and not root_deleted:
                forest.append(node)
            node.left = helper(node.left, root_deleted)
            node.right = helper(node.right, root_deleted)
            return None if root_deleted else node

        helper(root, True)
        return forest
      

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        unordered_set<int> to_delete_set(to_delete.begin(), to_delete.end());
        vector<TreeNode*> forest;
        helper(root, true, to_delete_set, forest);
        return forest;
    }
    
    TreeNode* helper(TreeNode* node, bool is_root, unordered_set<int>& to_delete_set, vector<TreeNode*>& forest) {
        if (!node) return nullptr;
        bool root_deleted = to_delete_set.count(node->val);
        if (is_root && !root_deleted) {
            forest.push_back(node);
        }
        node->left = helper(node->left, root_deleted, to_delete_set, forest);
        node->right = helper(node->right, root_deleted, to_delete_set, forest);
        return root_deleted ? nullptr : node;
    }
};
      

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        Set<Integer> toDeleteSet = new HashSet<>();
        for (int val : to_delete) toDeleteSet.add(val);
        List<TreeNode> forest = new ArrayList<>();
        helper(root, true, toDeleteSet, forest);
        return forest;
    }
    
    private TreeNode helper(TreeNode node, boolean isRoot, Set<Integer> toDeleteSet, List<TreeNode> forest) {
        if (node == null) return null;
        boolean rootDeleted = toDeleteSet.contains(node.val);
        if (isRoot && !rootDeleted) {
            forest.add(node);
        }
        node.left = helper(node.left, rootDeleted, toDeleteSet, forest);
        node.right = helper(node.right, rootDeleted, toDeleteSet, forest);
        return rootDeleted ? null : node;
    }
}
      

/**
 * 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 toDeleteSet = new Set(to_delete);
    const forest = [];

    function helper(node, isRoot) {
        if (!node) return null;
        const rootDeleted = toDeleteSet.has(node.val);
        if (isRoot && !rootDeleted) {
            forest.push(node);
        }
        node.left = helper(node.left, rootDeleted);
        node.right = helper(node.right, rootDeleted);
        return rootDeleted ? null : node;
    }

    helper(root, true);
    return forest;
};
      

Problem Description

You are given the root of a binary tree and a list of integer values called to_delete. Your task is to delete all nodes with values present in to_delete from the tree. After deleting a node, any of its children that are not deleted should become roots of new trees in the resulting forest.

Return a list of the roots of the trees in the forest after all deletions. Each tree in the forest should not contain any node with a value in to_delete. You should not reuse or duplicate nodes—each node must appear in at most one tree in the output forest.

Constraints:

• All node values are unique.
• There is at least one node in the tree.
• There is at least one value in to_delete.
• One valid solution exists for the input.

Thought Process

The problem asks us to remove certain nodes from a binary tree and return the resulting "forest" (a collection of trees). At first glance, one might consider traversing the tree, deleting nodes as they are found, and then collecting the remaining roots. However, this is tricky because deleting a node can turn its children into new roots, and we need to avoid duplicating or missing any subtree.

A brute-force approach might involve multiple passes: one to delete nodes, another to find new roots, and so on. But this is inefficient and error-prone. Instead, we can take a more systematic approach by using recursion. The recursive function can decide, at each node:

• Should this node be deleted?
• If so, should its children become new roots?

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Use a Set for Deletions: Store all values in to_delete in a set for O(1) lookups during traversal.
2. Recursive Traversal: Define a helper function that takes a node and a boolean flag is_root (indicating if the current node is a root of a tree).
3. Process Children First: Recursively process the left and right children, passing root_deleted as the new is_root flag. This ensures that if the current node is deleted, its non-deleted children become roots.
4. Delete or Keep Node: If the current node's value is in the to_delete set, return null (or None), effectively deleting it.
5. Collect Roots: If the current node is a root and is not deleted, add it to the result list (the forest).
6. Return the Result: After the recursive traversal, the result list will contain all the roots of the trees in the forest.

This approach ensures that each node is visited only once, and all deletions and new roots are handled in a single traversal.

Example Walkthrough

Sample Input:
Tree:
    1
  /    \
 2     3
/ \    / \
4 5  6 7

to_delete = [3, 5]

Step-by-step:

1. Start at root (1). 1 is not deleted, so it remains a root.
2. Go to left child (2). 2 is not deleted.
3. Left child of 2 is 4 (not deleted). 4 remains attached to 2.
4. Right child of 2 is 5 (to be deleted). Remove 5. Since 5 is deleted and has no children, nothing is added.
5. Back to 2: its right child is now null.
6. Go to right child of root (3). 3 is to be deleted. Its children (6 and 7) are not deleted, so both become new roots in the forest.
7. After traversal, the forest consists of trees rooted at 1, 6, and 7.

Time and Space Complexity

Brute-force approach: If we attempted to scan and reconstruct the tree multiple times, the time complexity could be O(N * D), where N is the number of nodes and D is the number of deletions, since each deletion might require a full scan.

Optimized approach: With the recursive solution:

• Time Complexity: O(N), since each node is visited exactly once.
• Space Complexity: O(N), for the recursion stack in the worst case (a skewed tree) and for the output list (forest).

Summary

The key insight is to use a post-order traversal with a helper function that can delete nodes and promote their children to new roots if needed. By leveraging a set for fast deletion checks and carefully managing the recursion, we ensure all deletions and root assignments are handled efficiently in a single pass. This makes the solution both elegant and optimal for the problem.