Delete Nodes And Return Forest

Medium Trees & BST Postorder + Multiple Return Values Original on LeetCode

Delete Nodes And Return Forest is a medium trees & bst problem solved with the postorder + multiple return values pattern. The best approach, optimal (postorder dfs with a hash set), runs in O(n + k) time and O(n + k) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (delete one value at a time) up.

Problem

You are given the root of a binary tree whose node values are all different, and an array toDelete of values. Remove every node whose value is in toDelete.

Removing nodes splits the tree into a forest of smaller trees. Return the roots of all remaining trees, in any order.

Examples

Example 1

Input
root = [1, 2, 3, 4, 5, 6, 7], toDelete = [3, 5]
Output
[[1, 2, null, 4], [6], [7]]
Why
Removing 3 frees its children 6 and 7 as new trees; removing 5 just cuts a leaf from 2.

Example 2

Input
root = [4, 2, 6, 1, 3], toDelete = [4]
Output
[[2, 1, 3], [6]]
Why
Deleting the root leaves its two subtrees as separate trees.

Example 3

Input
root = [1, 2, null, 3], toDelete = [2]
Output
[[1], [3]]
Why
The middle node disappears; 1 keeps no children and 3 becomes a root.

Constraints

  • The tree has between 1 and 1000 nodes.
  • Node values are distinct and between 1 and 1000.
  • toDelete has at most 1000 distinct values, each of which is in the tree.
  • The trees in the answer may be listed in any order.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (delete one value at a time)O(n · k)O(n)
Optimal (postorder DFS with a hash set)O(n + k)O(n + k)

1Brute force (delete one value at a time)

TimeO(n · k)Each of the k deletions may search all n nodes.
SpaceO(n)The forest list and the recursion stack.

Keep the current forest as a list of roots. For each value to delete, search every tree for that node and its parent, cut it out and add its children as new roots.

  1. Start with forest = [root].
  2. For each value v: search each tree with a DFS that also remembers the parent.
  3. When found, detach it from its parent (or remove its tree if it was a root) and add its non-null children to the forest.
class Solution {
    private TreeNode found, foundParent;

    public List<TreeNode> delNodes(TreeNode root, int[] toDelete) {
        List<TreeNode> forest = new ArrayList<>();
        forest.add(root);
        for (int v : toDelete) {
            for (int t = 0; t < forest.size(); t++) {
                found = null;
                foundParent = null;
                search(forest.get(t), null, v);
                if (found == null) continue;
                if (foundParent == null) forest.remove(t);
                else if (foundParent.left == found) foundParent.left = null;
                else foundParent.right = null;
                if (found.left != null) forest.add(found.left);
                if (found.right != null) forest.add(found.right);
                break;
            }
        }
        return forest;
    }

    private void search(TreeNode node, TreeNode parent, int v) {
        if (node == null || found != null) return;
        if (node.val == v) {
            found = node;
            foundParent = parent;
            return;
        }
        search(node.left, node, v);
        search(node.right, node, v);
    }
}

2Optimal (postorder DFS with a hash set)

TimeO(n + k)Every node is visited once and each set lookup is O(1) on average.
SpaceO(n + k)The set of k values, the recursion stack (up to the tree height) and the answer list.

Put the values to delete into a hash set and run one postorder DFS. Each call first fixes its children (setting a child pointer to whatever the child call returns), then, if the current node is deleted, adds its surviving children as new roots and returns null so the parent drops it. The original root is a root of the answer if it survives.

  1. Store toDelete in a set.
  2. dfs(node): if null return null; node.left = dfs(node.left); node.right = dfs(node.right).
  3. If node is deleted: add its non-null children to the answer and return null; otherwise return node.
  4. Call dfs(root); if it returns non-null, add root to the answer.
class Solution {
    private Set<Integer> del;
    private List<TreeNode> forest;

    public List<TreeNode> delNodes(TreeNode root, int[] toDelete) {
        del = new HashSet<>();
        for (int v : toDelete) del.add(v);
        forest = new ArrayList<>();
        if (dfs(root) != null) forest.add(root);
        return forest;
    }

    private TreeNode dfs(TreeNode node) {
        if (node == null) return null;
        node.left = dfs(node.left);
        node.right = dfs(node.right);
        if (!del.contains(node.val)) return node;
        if (node.left != null) forest.add(node.left);
        if (node.right != null) forest.add(node.right);
        return null;
    }
}

Edge cases to test

  • Deleting the root
  • Deleting every node (the answer is empty)
  • Empty toDelete (the answer is the original tree)
  • Deleting a parent and its child at the same time

Hints

Hint 1

A node starts a new tree exactly when it survives and its parent is deleted (or it is the original root).

Hint 2

If you process children before their parent (postorder), each call can tell its parent "I am gone, set your pointer to null" by returning null.

FAQ

What is the best time complexity for Delete Nodes And Return Forest?

Optimal (postorder DFS with a hash set) runs in O(n + k) time and O(n + k) extra space. Every node is visited once and each set lookup is O(1) on average.

Which pattern does Delete Nodes And Return Forest use?

It is a trees & bst problem that uses the postorder + multiple return values pattern. Other problems with the same pattern: Balanced Binary Tree, Validate Binary Search Tree, Children Sum in a Binary Tree.

Is there a brute force solution for Delete Nodes And Return Forest?

Yes. Brute force (delete one value at a time) takes O(n · k) time and O(n) space. Keep the current forest as a list of roots.

Which edge cases should I test for Delete Nodes And Return Forest?

Deleting the root; Deleting every node (the answer is empty); Empty toDelete (the answer is the original tree); Deleting a parent and its child at the same time.