Problem Description

You are given the root of a binary tree where each node has a distinct value. You also have a list of values called to_delete that specifies which nodes should be removed from the tree.

When you delete a node from the tree, the tree may split into multiple smaller trees (a forest). Specifically, when a node is deleted:

• Its parent (if it exists) will no longer point to it
• Its children (if they exist) become roots of new separate trees

Your task is to delete all nodes whose values appear in to_delete and return a list containing the root nodes of all the remaining trees in the forest.

For example, if you have a tree and delete a node in the middle, you might end up with:

• The original root (if it wasn't deleted) leading a smaller tree
• The deleted node's left child (if it exists) becoming the root of a new tree
• The deleted node's right child (if it exists) becoming the root of another new tree

The key points to understand:

• Each node value in the tree is unique
• After deletion, you need to collect all the "new" root nodes
• A node becomes a new root if its parent was deleted but the node itself wasn't deleted
• The original root remains a root (and should be included) only if it wasn't deleted
• You can return the roots in any order

The solution uses a depth-first search (DFS) approach that processes nodes from bottom to top, handling deletions and collecting new roots as it traverses back up the tree.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a binary tree, which is a special type of graph with nodes (tree nodes) and edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure where each node has at most two children (left and right).

DFS

• Yes: We arrive at DFS as the solution pattern.

The flowchart leads us directly to DFS because:

1. We're dealing with a tree data structure
2. We need to traverse the entire tree to identify nodes to delete
3. We need to process nodes and their relationships (parent-child connections)
4. When deleting a node, we need to handle its subtrees, which requires visiting all nodes in a systematic way

Why DFS is the right choice for this problem:

• Bottom-up processing: DFS allows us to process children before their parents (post-order traversal), which is crucial here because we need to decide what to do with children before deleting their parent
• Tree modification: We need to modify the tree structure by removing nodes and potentially creating new trees, which is naturally handled through recursive DFS
• Collecting roots: As we traverse and delete nodes, DFS helps us identify and collect new root nodes when their parents are deleted

Conclusion: The flowchart correctly identifies DFS as the optimal approach for this tree modification problem where we need to delete specific nodes and return the resulting forest of trees.

Intuition

When we delete a node from a tree, we're essentially "cutting" the tree at that point. The key insight is that this cutting action creates new independent trees from the deleted node's children (if they exist and aren't also being deleted).

Think about it this way: imagine cutting a branch from a real tree. The part above the cut (toward the root) remains with the main tree, while the part below the cut falls off. But in our problem, when we "cut" (delete) a node, both its children become new independent trees.

The challenge is determining which nodes become new roots. A node becomes a new root in exactly one scenario: when its parent is deleted but the node itself survives. This means we need to track:

1. Whether a node should be deleted
2. Whether its children should become new roots

The natural way to handle this is to process the tree from bottom to top using post-order traversal (process children before parents). Why? Because when we reach a parent node, we need to already know what happened to its children:

• If a child was deleted, the parent should point to null instead
• If a child survived, we need to decide if it becomes a new root based on whether the parent will be deleted

Here's the clever part: we can use the return value of our recursive function to signal whether a node survives or not:

• Return null if the node is deleted (telling the parent to disconnect)
• Return the node itself if it survives (telling the parent to keep the connection)

When we delete a node, before returning null, we check its children. If they exist (aren't null), they must be surviving nodes that now become new roots, so we add them to our answer list.

The original root is special - if it survives the deletion process, it remains a root and should be added to our answer. This is why we check the final return value of our DFS call on the root.

Using a set for to_delete values gives us O(1) lookup time, making the deletion check efficient as we traverse through the tree.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The solution uses a depth-first search (DFS) with post-order traversal to process the tree from bottom to top. Here's how the implementation works:

Data Structure Setup:

• Convert the to_delete list into a set s for O(1) lookup time when checking if a node should be deleted
• Initialize an empty list ans to collect all the root nodes of the resulting forest

The DFS Function: The core logic is in the recursive dfs(root) function that returns either the node itself (if it survives) or None (if it's deleted):

1. Base Case: If root is None, return None immediately

2. Recursive Processing:

   • First recursively call dfs(root.left) and dfs(root.right)
   • Assign the return values back to root.left and root.right
   • This ensures children are processed before their parent (post-order)
   • This also automatically updates the tree structure - deleted children become None

3. Decision Logic:

   • Check if root.val is in the deletion set s
   • If the node should NOT be deleted: Simply return root (the node survives with its updated children)
   • If the node should be deleted:
     • Check if root.left exists (not None) - if yes, it becomes a new root, so add it to ans
     • Check if root.right exists (not None) - if yes, it becomes a new root, so add it to ans
     • Return None to signal to the parent that this node is deleted

Main Function Logic: After defining the DFS function:

1. Call dfs(root) on the original root
2. If the return value is not None (meaning the original root survived), add it to ans
3. Return the ans list containing all roots of the forest

Why This Works:

• By processing bottom-up, when we delete a node, its children have already been processed and we know exactly which ones survived
• The return value cleverly serves dual purposes: updating parent pointers and signaling node survival
• Children of deleted nodes automatically become roots because they're added to ans right before their parent returns None
• The tree structure is modified in-place as we traverse, with deleted nodes being disconnected by setting references to None

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• Binary tree:

        1
       / \
      2   3
     / \
    4   5

• to_delete = [2]

Step-by-step DFS traversal (post-order):

1. Start DFS from root (1)

   • First, recursively process left child (2)

2. DFS on node 2

   • Recursively process its left child (4)

3. DFS on node 4

   • Node 4 has no children, so dfs(None) returns None for both
   • Node 4's value (4) is NOT in to_delete
   • Return node 4 itself

4. Back to node 2, process right child (5)

   • Node 5 has no children
   • Node 5's value (5) is NOT in to_delete
   • Return node 5 itself

5. Back to node 2 - decision time

   • root.left = node 4 (from step 3)
   • root.right = node 5 (from step 4)
   • Node 2's value (2) IS in to_delete = [2]
   • Since node 2 will be deleted:
     • Check left child: node 4 exists → add to ans (it becomes a new root)
     • Check right child: node 5 exists → add to ans (it becomes a new root)
   • Return None (node 2 is deleted)

6. Back to root (1), process right child (3)

   • Node 3 has no children
   • Node 3's value (3) is NOT in to_delete
   • Return node 3 itself

7. Back to root (1) - final decision

   • root.left = None (from step 5, since node 2 was deleted)
   • root.right = node 3 (from step 6)
   • Node 1's value (1) is NOT in to_delete
   • Return node 1 itself

8. Main function finale

   • DFS returned node 1 (not None)
   • Add node 1 to ans
   • Final ans = [node 4, node 5, node 1]

Resulting forest:

Tree 1:    1        Tree 2:    4        Tree 3:    5
            \
             3

The deletion of node 2 split the original tree into three separate trees with roots 1, 4, and 5.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a depth-first search (DFS) traversal of the binary tree. Each node in the tree is visited exactly once during the traversal. At each node, the following operations are performed:

• Recursive calls to process left and right children
• Checking if the node's value exists in the set s (which is O(1) average case for set lookup)
• Potentially appending child nodes to the result list (which is O(1) for list append)

Since we visit all n nodes exactly once and perform constant-time operations at each node, the overall time complexity is O(n).

Space Complexity: O(n)

The space complexity consists of several components:

• The set s stores the values to delete, which takes O(m) space where m is the size of to_delete. In the worst case, m could be O(n).
• The recursion call stack can go as deep as the height of the tree. In the worst case (skewed tree), this could be O(n). In the best case (balanced tree), it would be O(log n).
• The result list ans stores the roots of the remaining forest. In the worst case, if we delete all internal nodes and keep only leaf nodes, we could have up to O(n) trees in the result.

Taking the worst-case scenario for all components, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Add the Original Root to the Result

One of the most common mistakes is forgetting to check if the original root survives the deletion process and should be added to the result list. Many developers focus on collecting the children of deleted nodes as new roots but overlook that the original root itself might still be a valid root.

Incorrect approach:

def delNodes(self, root, to_delete):
    to_delete_set = set(to_delete)
    forest_roots = []
  
    def dfs(node):
        if not node:
            return None
      
        node.left = dfs(node.left)
        node.right = dfs(node.right)
      
        if node.val in to_delete_set:
            if node.left:
                forest_roots.append(node.left)
            if node.right:
                forest_roots.append(node.right)
            return None
      
        return node
  
    dfs(root)  # ❌ Forgot to check if root survived!
    return forest_roots

Solution: Always check the return value of dfs(root). If it's not None, the original root survived and should be added to the result:

if dfs(root):  # ✅ Check if root survived
    forest_roots.append(root)

2. Adding Children to Result Before They're Fully Processed

Another pitfall is adding children nodes to the result before recursively processing them, which can lead to including nodes that should actually be deleted.

Incorrect approach:

def dfs(node):
    if not node:
        return None
  
    if node.val in to_delete_set:
        # ❌ Adding children before processing them
        if node.left:
            forest_roots.append(node.left)
        if node.right:
            forest_roots.append(node.right)
      
        # Then processing children
        dfs(node.left)
        dfs(node.right)
        return None
  
    node.left = dfs(node.left)
    node.right = dfs(node.right)
    return node

Solution: Always process children first (post-order traversal) and use the return values to determine which children survived:

# ✅ Process children first
node.left = dfs(node.left)
node.right = dfs(node.right)

# Then check if current node should be deleted
if node.val in to_delete_set:
    # Now we know which children survived (non-None)
    if node.left:
        forest_roots.append(node.left)
    if node.right:
        forest_roots.append(node.right)
    return None

3. Not Using a Set for to_delete Lookup

Using the list directly for membership checking leads to O(n) lookup time for each node, making the overall complexity unnecessarily high.

Inefficient approach:

# ❌ O(n) lookup for each node check
if node.val in to_delete:  # to_delete is a list
    # deletion logic

Solution: Convert the list to a set at the beginning for O(1) lookup:

# ✅ O(1) lookup
to_delete_set = set(to_delete)
if node.val in to_delete_set:
    # deletion logic