Delete Nodes And Return Forest - Practice Coding Problems

Delete Nodes And Return Forest - 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.

Input & Output

Example 1 — Basic Deletion

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

› Output: [[1,2,null,4],[6],[7]]

💡 Note: Delete nodes 3 and 5. Node 1 remains as root of tree [1,2,null,4]. Children 6 and 7 of deleted node 3 become separate tree roots.

Example 2 — Root Deletion

$ Input: root = [1,2,4,null,3], to_delete = [1]

› Output: [[2,null,3],[4]]

💡 Note: Delete root node 1. Its children 2 and 4 become new tree roots. Node 3 remains as child of 2.

Example 3 — Single Node

$ Input: root = [1], to_delete = [1]

› Output: []

💡 Note: Delete the only node, resulting in an empty forest.

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.

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree [1,2,3,4,5,6,7] with delete list [3,5]

Delete Process

Remove nodes 3 and 5, children become new roots

Forest Result

Three separate trees: [1,2,null,4], [6], [7]

Key Takeaway

🎯 Key Insight: Deleted nodes split the tree - their children become forest roots

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is that when a node is deleted, its children become new tree roots. The optimal approach uses a single DFS traversal with a boolean flag to track root status. Time: O(n), Space: O(h + k)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Reconstruction	O(n × k)	O(h)	Delete nodes one by one and reconstruct the forest each time
DFS with Forest Collection	O(n)	O(h + k)	Single DFS traversal that deletes nodes and collects forest roots

Brute Force Reconstruction — Algorithm Steps

For each value in to_delete, find and remove that node
After each deletion, traverse remaining tree to find all roots
Collect all disconnected subtrees as separate trees

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Tree

Start with complete binary tree

Delete First Node

Remove first target node, rebuild remaining parts

Delete Second Node

Remove second target node, rebuild again

Final Forest

Collect all remaining tree roots

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int** solution(int* root, int rootSize, int* to_delete, int deleteSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    if (rootSize == 0) return NULL;
    
    bool toDeleteSet[1001] = {false};
    for (int i = 0; i < deleteSize; i++) {
        toDeleteSet[to_delete[i]] = true;
    }
    
    int** result = (int**)malloc(1000 * sizeof(int*));
    *returnColumnSizes = (int*)malloc(1000 * sizeof(int));
    
    struct TreeNode* buildTree(int* arr, int size, int index) {
        if (index >= size || arr[index] == -1) return NULL;
        struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        node->val = arr[index];
        node->left = buildTree(arr, size, 2 * index + 1);
        node->right = buildTree(arr, size, 2 * index + 2);
        return node;
    }
    
    int* treeToArray(struct TreeNode* root, int* size) {
        if (!root) {
            *size = 0;
            return NULL;
        }
        int* arr = (int*)malloc(1000 * sizeof(int));
        int front = 0, rear = 0;
        struct TreeNode* queue[1000];
        queue[rear++] = root;
        *size = 0;
        
        while (front < rear) {
            struct TreeNode* node = queue[front++];
            if (node) {
                arr[(*size)++] = node->val;
                queue[rear++] = node->left;
                queue[rear++] = node->right;
            }
        }
        return arr;
    }
    
    struct TreeNode* deleteAndCollect(struct TreeNode* node, bool isRoot) {
        if (!node) return NULL;
        
        bool deleted = toDeleteSet[node->val];
        
        if (isRoot && !deleted) {
            int size;
            result[*returnSize] = treeToArray(node, &size);
            (*returnColumnSizes)[*returnSize] = size;
            (*returnSize)++;
        }
        
        node->left = deleteAndCollect(node->left, deleted);
        node->right = deleteAndCollect(node->right, deleted);
        
        return deleted ? NULL : node;
    }
    
    struct TreeNode* rootNode = buildTree(root, rootSize, 0);
    deleteAndCollect(rootNode, true);
    
    return result;
}

int main() {
    // Input parsing for array format would be complex in C
    // This is a simplified version
    int root[] = {1, 2, 3, 4, 5, 6, 7};
    int to_delete[] = {3, 5};
    int returnSize;
    int* returnColumnSizes;
    
    int** result = solution(root, 7, to_delete, 2, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            if (j > 0) printf(",");
            printf("%d", result[i][j]);
        }
        printf("]");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k)

n nodes × k deletions, each requiring full tree traversal

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth up to tree height h

✓ Linear Space

78.9K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Reconstruction — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler