Delete Nodes And Return Forest

MediumTrees · DFS (Post-order Pruning)🧩 Tree DFS LeetCode #1110 ↗Updated Oct 30, 2026

Problem

You get the root of a binary tree whose values are all distinct, plus an array to_delete. Remove every node whose value is listed. Cutting those nodes out splits the tree into several smaller trees (a forest); return the root of each remaining tree, in any order.

Inputroot = [1,2,3,4,5,6,7], to_delete = [2]Output[[1,null,3,6,7],[4],[5]]

Inputroot = [5,3,8,1,4], to_delete = [5]Output[[3,1,4],[8]]

Inputroot = [1], to_delete = [1]Output[]

1 ≤ nodes ≤ 1000 · 1 ≤ Node.val ≤ 1000, all distinct · to_delete.length ≤ 1000, distinct values in [1, 1000]

Try it yourself

Java

class Solution {
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A surviving node becomes a new root exactly when its parent is deleted (or it is the original root). Pass “is my parent gone?” down the recursion and let each call return null if its node is deleted — the parent simply re-assigns its child pointer to that return value.

PatternTree DFS

Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.

Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.

Open the Tree DFS guide →

Approaches

Brute ForceSearch & Cut One Value at a Time

Time O(n · k)Space O(n)

Keep a list of current roots. For each value to delete, scan every tree in the forest until the node is found: if it is a root, drop it from the list; otherwise unlink it from its parent. Either way its non-null children are promoted to roots.

Java

public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
    List<TreeNode> forest = new ArrayList<>();
    if (root != null) forest.add(root);
    for (int target : to_delete) {
        for (int i = 0; i < forest.size(); i++) {
            TreeNode tree = forest.get(i);
            if (tree.val == target) {
                forest.remove(i);
                promoteChildren(tree, forest);
                break;
            }
            if (cutBelow(tree, target, forest)) break;
        }
    }
    return forest;
}
// Looks for target among the descendants of parent and unlinks it if found.
private boolean cutBelow(TreeNode parent, int target, List<TreeNode> forest) {
    if (parent == null) return false;
    if (parent.left != null && parent.left.val == target) {
        promoteChildren(parent.left, forest);
        parent.left = null;
        return true;
    }
    if (parent.right != null && parent.right.val == target) {
        promoteChildren(parent.right, forest);
        parent.right = null;
        return true;
    }
    return cutBelow(parent.left, target, forest) || cutBelow(parent.right, target, forest);
}
private void promoteChildren(TreeNode node, List<TreeNode> forest) {
    if (node.left != null) forest.add(node.left);
    if (node.right != null) forest.add(node.right);
}

Direct simulation, but each of the k deletions may rescan the whole forest.

BetterBFS with a Delete Set

Time O(n + k)Space O(n + k)

Load to_delete into a hash set, then walk the tree once with a queue. For every node, look at each child: a deleted child is unlinked; a kept child whose parent is deleted becomes a new root. Every node is processed once, no matter how many values are deleted.

Java

public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
    Set<Integer> del = new HashSet<>();
    for (int v : to_delete) del.add(v);
    List<TreeNode> forest = new ArrayList<>();
    if (root == null) return forest;
    if (!del.contains(root.val)) forest.add(root);
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        boolean gone = del.contains(node.val);
        TreeNode left = node.left, right = node.right;
        if (left != null) {
            queue.offer(left);
            if (del.contains(left.val)) node.left = null;
            else if (gone) forest.add(left); // parent removed -> new root
        }
        if (right != null) {
            queue.offer(right);
            if (del.contains(right.val)) node.right = null;
            else if (gone) forest.add(right);
        }
    }
    return forest;
}

Linear and iterative, but the queue can hold a whole level and the logic is split per child.

OptimalRecursive Pruning (Return null if Deleted)

Time O(n + k)Space O(h)

prune(node, parentGone) records node as a root when it survives and its parent does not. It then rebuilds its own child links from the recursive results and returns null if it is deleted itself, so the parent's pointer is fixed automatically. Values are ≤ 1000, so a boolean[1001] replaces the hash set.

Java

public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
    boolean[] del = new boolean[1001];
    for (int v : to_delete) del[v] = true;
    List<TreeNode> forest = new ArrayList<>();
    prune(root, true, del, forest);
    return forest;
}
private TreeNode prune(TreeNode node, boolean parentGone, boolean[] del,
                       List<TreeNode> forest) {
    if (node == null) return null;
    boolean gone = del[node.val];
    if (parentGone && !gone) forest.add(node); // top of a surviving piece
    node.left = prune(node.left, gone, del, forest);
    node.right = prune(node.right, gone, del, forest);
    return gone ? null : node;
}

One pass, no queue, and the pointer surgery is a single assignment per child.

Pro tip

Returning the (possibly null) subtree and assigning it back to node.left/node.right is the standard trick for any “remove nodes from a tree” problem.

At a glance

Level	Approach	Time	Space
Brute Force	Search & Cut One Value at a Time	`O(n · k)`	`O(n)`
Better	BFS with a Delete Set	`O(n + k)`	`O(n + k)`
Optimal	Recursive Pruning (Return null if Deleted)	`O(n + k)`	`O(h)`

Common pitfalls

Forgetting to null out the parent's pointer to a deleted child — the deleted node stays inside a returned tree.
Adding a child as a new root when it is itself in to_delete.
Forgetting the original root: it is a forest root if (and only if) it is not deleted.

Interview tips

State the rule first: “a kept node is a root iff its parent was deleted or it is the root”.
Explain why post-order style assignment (node.left = prune(...)) fixes links for free.
Mention the set vs. boolean-array choice and that output order does not matter.

Pattern

Tree DFS returning a rebuilt subtree → whenever nodes are removed or replaced and parents must update their child pointers.

My notes saved in this browser