LeetCode Problem 1110

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Tree, Depth-First Search, Binary Tree

Solution

LeetCode 1110 - Delete Nodes And Return Forest

Problem Understanding

This problem gives us the root of a binary tree and a list of node values that must be deleted from the tree. Every node value in the tree is unique, which is important because it means we can identify nodes directly by value without ambiguity.

When a node is deleted, it is completely removed from the tree. Its parent loses the connection to it. However, the deleted node’s children are not automatically deleted unless their values also appear in to_delete. If those children remain valid, they become new roots in the resulting forest.

The final output is not a single tree, but a collection of disconnected trees. This collection is called a forest. We must return the root node of every remaining tree after all deletions are complete.

For example, consider this tree:

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

If we delete nodes 3 and 5:

• Node 3 is removed.
• Its children 6 and 7 are not deleted, so they become new roots.
• Node 5 is removed.
• Node 1 remains the root of the original tree.

The resulting forest contains:

    1         6       7
   /
  2
 /
4

The constraints are relatively small:

• At most 1000 nodes
• Node values are between 1 and 1000
• Values are distinct

Because the tree size is small, an O(n) or O(n log n) solution is more than sufficient. However, we still want an efficient traversal because repeatedly searching the delete list could become unnecessarily expensive.

Several edge cases are important:

• The root itself may be deleted.
• Every node may be deleted.
• No nodes may be deleted.
• A deleted node may have surviving children that must become new roots.
• Leaf nodes may be deleted.
• The tree may be highly unbalanced.

The problem guarantees unique node values, which allows efficient lookup using a hash set.

Approaches

Brute Force Approach

A straightforward solution is to process each value in to_delete one at a time. For every deletion value, we could traverse the entire tree to find the node and its parent, disconnect the node, and then determine whether its children should become new roots.

This works because eventually every node marked for deletion gets removed correctly. However, the inefficiency comes from repeatedly scanning the tree.

If there are n nodes and d deletion values, we may end up traversing the tree d times. In the worst case:

• n = 1000
• d = 1000

This leads to O(n * d) complexity, which becomes O(n²) in the worst case.

Although the constraints are small enough that this could still pass, it is unnecessarily inefficient and more complicated to implement correctly because tree structure changes during repeated deletions.

Optimal Approach

The key insight is that deletions naturally fit a postorder tree traversal.

When deciding whether to delete a node, we first need to know what happened to its children. If a child was deleted, the current node’s pointer to that child should become None. This means children must be processed before parents.

That is exactly what postorder traversal does:

1. Process left subtree
2. Process right subtree
3. Process current node

We also use a hash set for to_delete so membership checks are O(1).

During DFS:

• Recursively process children first.

• Update child pointers after recursion.

• If the current node should be deleted:

• Add surviving children to the forest.

• Return None to the parent.

• Otherwise return the current node.

Finally, if the original root is not deleted, it must be included in the forest.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(h)	Repeatedly traverses tree for each deletion
Optimal	O(n)	O(h + d)	Single DFS traversal with hash set lookups

Here:

• n is the number of nodes
• h is tree height
• d is the size of to_delete

Algorithm Walkthrough

1. Convert to_delete into a hash set.

We need to frequently check whether a node should be deleted. A hash set gives average O(1) lookup time, which is much faster than scanning a list repeatedly. 2. Create an empty result list called forest.

This list stores the roots of all remaining trees after deletions. 3. Define a recursive DFS function.

The DFS function processes a subtree and returns the updated root after deletions. 4. Recursively process the left child.

The returned value may be:

• The original child node if it survives
• None if the child was deleted

We assign this returned value back to node.left. 5. Recursively process the right child.

The same logic applies to the right subtree. 6. Check whether the current node should be deleted.

If node.val exists in the delete set:

• Any surviving left child becomes a new forest root.
• Any surviving right child becomes a new forest root.
• Return None so the parent disconnects this node.

7. If the current node is not deleted, return the node itself.

This preserves the subtree connection. 8. Process the original root with DFS.

The returned value tells us whether the original root survives. 9. If the root survives, add it to the forest.

Since it has no parent, it remains a valid tree root. 10. Return the forest list.

Why it works

The algorithm works because postorder traversal guarantees that children are fully processed before their parent is evaluated. By the time we decide whether to delete a node, we already know:

• Which children survived
• Which children were removed
• Which children should become new roots

Returning None cleanly removes deleted nodes from the tree, while adding surviving children to the forest preserves all disconnected subtrees correctly.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
        delete_set = set(to_delete)
        forest = []

        def dfs(node: Optional[TreeNode]) -> Optional[TreeNode]:
            if not node:
                return None

            node.left = dfs(node.left)
            node.right = dfs(node.right)

            if node.val in delete_set:
                if node.left:
                    forest.append(node.left)

                if node.right:
                    forest.append(node.right)

                return None

            return node

        root = dfs(root)

        if root:
            forest.append(root)

        return forest

The implementation begins by converting to_delete into a set for efficient lookup. This prevents repeated linear searches during traversal.

The recursive dfs function handles all subtree processing. The base case returns None when the node is empty.

The recursive calls process the left and right subtrees first. Their returned values are reassigned back to node.left and node.right. This is important because deleted children return None, effectively disconnecting them from the parent.

After processing children, the algorithm checks whether the current node should be deleted.

If the node must be removed:

• Surviving children are added to the forest because they become independent trees.
• The function returns None, signaling the parent to disconnect this node.

If the node survives, it is returned unchanged.

Finally, after DFS finishes, the original root is added to the forest only if it still exists.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func delNodes(root *TreeNode, to_delete []int) []*TreeNode {
    deleteSet := make(map[int]bool)

    for _, val := range to_delete {
        deleteSet[val] = true
    }

    forest := []*TreeNode{}

    var dfs func(node *TreeNode) *TreeNode

    dfs = func(node *TreeNode) *TreeNode {
        if node == nil {
            return nil
        }

        node.Left = dfs(node.Left)
        node.Right = dfs(node.Right)

        if deleteSet[node.Val] {
            if node.Left != nil {
                forest = append(forest, node.Left)
            }

            if node.Right != nil {
                forest = append(forest, node.Right)
            }

            return nil
        }

        return node
    }

    root = dfs(root)

    if root != nil {
        forest = append(forest, root)
    }

    return forest
}

The Go implementation follows the same recursive logic as the Python version.

Instead of a Python set, Go uses a map[int]bool for constant time membership checks.

Go uses nil instead of Python’s None. Returning nil from DFS disconnects deleted nodes from their parents.

Slices are dynamically expanded using append, which is how the forest list is maintained.

Because the constraints are small, recursion depth is safe within typical Go stack limits.

Worked Examples

Example 1

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

Initial tree:

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

Delete set:

{3, 5}

DFS Traversal Order

Postorder traversal visits:

4 → 5 → 2 → 6 → 7 → 3 → 1

Step-by-Step Trace

Current Node	Deleted?	Action	Forest
4	No	Return node 4	[]
5	Yes	Delete node 5	[]
2	No	Left=4, Right=None	[]
6	No	Return node 6	[]
7	No	Return node 7	[]
3	Yes	Add 6 and 7 to forest	[6, 7]
1	No	Left=2, Right=None	[6, 7]

After traversal:

• Root 1 survives
• Add 1 to forest

Final forest:

[1, 6, 7]

Resulting trees:

    1         6       7
   /
  2
 /
4

Example 2

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

Initial tree:

      1
     / \
    2   4
     \
      3

Delete set:

{3}

DFS Traversal Order

3 → 2 → 4 → 1

Step-by-Step Trace

Current Node	Deleted?	Action	Forest
3	Yes	Delete node 3	[]
2	No	Right becomes None	[]
4	No	Return node 4	[]
1	No	Tree remains connected	[]

Root 1 survives, so it is added to forest.

Final forest:

[1]

Resulting tree:

      1
     / \
    2   4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited exactly once
Space	O(h + d)	Recursion stack plus delete set

The DFS traversal processes every node one time, giving linear time complexity.

The recursion stack requires O(h) space, where h is the height of the tree. In the worst case of a skewed tree, this becomes O(n).

The delete set stores up to d values from to_delete.

Test Cases

# Helper functions for testing

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def serialize(root):
    if not root:
        return None

    return (
        root.val,
        serialize(root.left),
        serialize(root.right)
    )

# Solution implementation
class Solution:
    def delNodes(self, root, to_delete):
        delete_set = set(to_delete)
        forest = []

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

            node.left = dfs(node.left)
            node.right = dfs(node.right)

            if node.val in delete_set:
                if node.left:
                    forest.append(node.left)

                if node.right:
                    forest.append(node.right)

                return None

            return node

        root = dfs(root)

        if root:
            forest.append(root)

        return forest

sol = Solution()

# Test 1: Example 1
root = TreeNode(1,
    TreeNode(2,
        TreeNode(4),
        TreeNode(5)
    ),
    TreeNode(3,
        TreeNode(6),
        TreeNode(7)
    )
)

result = [serialize(tree) for tree in sol.delNodes(root, [3, 5])]
assert len(result) == 3  # verifies forest split

# Test 2: Example 2
root = TreeNode(1,
    TreeNode(2, None, TreeNode(3)),
    TreeNode(4)
)

result = [serialize(tree) for tree in sol.delNodes(root, [3])]
assert result == [
    (1, (2, None, None), (4, None, None))
]  # verifies leaf deletion

# Test 3: Delete root
root = TreeNode(1, TreeNode(2), TreeNode(3))

result = [serialize(tree) for tree in sol.delNodes(root, [1])]
assert len(result) == 2  # children become new roots

# Test 4: Delete nothing
root = TreeNode(1, TreeNode(2), TreeNode(3))

result = [serialize(tree) for tree in sol.delNodes(root, [])]
assert result == [
    (1, (2, None, None), (3, None, None))
]  # original tree remains unchanged

# Test 5: Delete all nodes
root = TreeNode(1, TreeNode(2), TreeNode(3))

result = sol.delNodes(root, [1, 2, 3])
assert result == []  # forest should be empty

# Test 6: Single node survives
root = TreeNode(1)

result = [serialize(tree) for tree in sol.delNodes(root, [])]
assert result == [
    (1, None, None)
]  # single-node tree remains

# Test 7: Single node deleted
root = TreeNode(1)

result = sol.delNodes(root, [1])
assert result == []  # deleting only node leaves empty forest

# Test 8: Skewed tree
root = TreeNode(1,
    TreeNode(2,
        TreeNode(3,
            TreeNode(4)
        )
    )
)

result = [serialize(tree) for tree in sol.delNodes(root, [2])]
assert len(result) == 1  # verifies subtree promotion

# Test 9: Delete internal node with surviving children
root = TreeNode(1,
    TreeNode(2,
        TreeNode(4),
        TreeNode(5)
    ),
    TreeNode(3)
)

result = [serialize(tree) for tree in sol.delNodes(root, [2])]
assert len(result) == 3  # children 4 and 5 become roots

Test Case Summary

Test	Why
Example 1	Verifies multiple deletions and forest splitting
Example 2	Verifies leaf deletion
Delete root	Ensures children become new roots
Delete nothing	Confirms original tree remains intact
Delete all nodes	Verifies empty forest handling
Single node survives	Tests smallest non-empty tree
Single node deleted	Tests smallest empty result
Skewed tree	Verifies recursion on unbalanced trees
Delete internal node	Ensures surviving children become roots

Edge Cases

Deleting the Root Node

One of the most important edge cases occurs when the root itself must be deleted. A naive implementation may accidentally lose access to the remaining subtrees.

For example:

    1
   / \
  2   3

If 1 is deleted, then 2 and 3 must become independent roots in the forest.

The implementation handles this correctly because when a deleted node is processed, any surviving children are immediately added to the forest before returning None.

Deleting Every Node

Another tricky case occurs when all nodes are deleted.

Example:

root = [1,2,3]
to_delete = [1,2,3]

The final forest should be empty.

A buggy implementation might accidentally keep references to deleted roots or append deleted nodes to the result list.

This solution avoids that problem because only surviving nodes are added to the forest. Since every DFS call returns None, no nodes remain.

Highly Unbalanced Trees

A skewed tree behaves more like a linked list:

1
 \
  2
   \
    3
     \
      4

Recursive tree algorithms sometimes fail on skewed structures if child references are not updated carefully after recursion.

This implementation correctly reconnects subtrees because each recursive call returns the updated subtree root. Whether a child survives or is deleted, the parent always receives the correct updated pointer.