Delete nodes and return forest

XXX. Delete Nodes and Return Forest

Tree

DFS

Problem Statement:

Given a binary tree root and an array of integers to_delete, delete all nodes with values in to_delete. After deleting a node, its children (if any) become separate trees in the forest. Return the roots of the trees in the forest in any order.

Algorithm:

1. Create a set toDeleteSet for faster lookup of nodes to delete.
2. Perform a post-order traversal of the tree:
   • Process left and right children recursively, updating them if they are deleted.
   • If a node is in toDeleteSet, add its children (if any) to the forest and return null to its parent to indicate deletion.
   • Otherwise, return the node itself to maintain its position in the tree.
3. After the traversal, check if the root itself was deleted. If not, add it to the forest.
4. Return the list of roots in the forest.

Complexity:

Time: O(n), where n is the number of nodes in the tree.
Space: O(n), for the recursion stack and the toDeleteSet.

Java Implementation:

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

    root = processNode(root, toDeleteSet, forest);

    // If the root is not deleted, add it to the forest
    if (root != null) forest.add(root);
    
    return forest;
}

private TreeNode processNode(TreeNode node, Set toDeleteSet, List forest) {
    if (node == null) return null;

    // Process left and right children recursively
    node.left = processNode(node.left, toDeleteSet, forest);
    node.right = processNode(node.right, toDeleteSet, forest);

    // Node Evaluation: Check if the current node needs to be deleted
    if (toDeleteSet.contains(node.val)) {
        // If the node has left or right children, add them to the forest
        if (node.left != null) forest.add(node.left);
        if (node.right != null) forest.add(node.right);
        
        // Return null to its parent to delete the current node
        return null;
    }

    return node;
}
                

Python Implementation:

def delNodes(root, to_delete):
    to_delete_set = set(to_delete)
    forest = []

    def processNode(node):
        if not node:
            return None

        # Process left and right children recursively
        node.left = processNode(node.left)
        node.right = processNode(node.right)

        # Check if the current node needs to be deleted
        if node.val in to_delete_set:
            if node.left:
                forest.append(node.left)
            if node.right:
                forest.append(node.right)
            return None
        return node

    root = processNode(root)
    if root:
        forest.append(root)
    return forest
                

C++ Implementation:

vector delNodes(TreeNode* root, vector& to_delete) {
    unordered_set toDeleteSet(to_delete.begin(), to_delete.end());
    vector forest;

    function processNode = [&](TreeNode* node) -> TreeNode* {
        if (!node) return nullptr;

        // Process left and right children recursively
        node->left = processNode(node->left);
        node->right = processNode(node->right);

        // Check if the current node needs to be deleted
        if (toDeleteSet.count(node->val)) {
            if (node->left) forest.push_back(node->left);
            if (node->right) forest.push_back(node->right);
            return nullptr;
        }
        return node;
    };

    root = processNode(root);
    if (root) forest.push_back(root);
    return forest;
}