Delete Nodes And Return Forest

LeetCode 1110: Delete Nodes And Return Forest Solution & Explanation

Problem Overview

TL;DR: Perform a postorder traversal to process children before parents, adding valid orphaned children to the result list while returning null to the parent to sever connections for deleted nodes.

The problem asks us to process a binary tree where each node has a unique value. We are given a list of values, to_delete. When a node is deleted, its children (if they exist and are not deleted themselves) become the roots of new disjoint trees. We must return a list containing the roots of all trees in the final forest. This is a classic structural modification problem found in interviews, often referred to as "Delete Nodes And Return Forest".

Brute Force Approach for Delete Nodes And Return Forest

A naive or brute force approach might attempt to simulate the deletion process iteratively or via multiple passes. One might search for a node to delete, remove it, store its children as new potential roots, and then restart the search process for the remaining values in to_delete.

Naive Algorithm Steps:

1. Create a queue of trees, initially containing just the original root.
2. For every value in to_delete: 3. Search every tree in the queue to find the node. 4. Once found, remove the node from its parent. 5. Add the deleted node's children to the queue of trees.
3. Repeat until all values are deleted.

Why this fails: While this approach works logically, it is inefficient. Searching for a node in a forest of trees takes $O(N)$ time. Doing this for $M$ nodes to delete results in $O(N \cdot M)$ complexity. Furthermore, managing the parent pointers and the collection of trees manually is error-prone and leads to complex, unmaintainable code. It does not leverage the recursive structure of the tree to perform deletions in a single pass.

Algorithm Strategy: Tree DFS - Recursive Postorder Traversal

1. Fast Lookups: Convert the to_delete array into a HashSet. This allows us to check if a node needs deletion in $O(1)$ time.
2. Recursive Function: Define a DFS helper function that takes the current node as input.
3. Postorder Traversal:
   • Recursively call the function on node.left and assign the result back to node.left.
   • Recursively call the function on node.right and assign the result back to node.right.
   • This ensures the tree structure below the current node is finalized before we process the current node.
4. Deletion Logic:
   • Check if node.val exists in the HashSet.
   • If deleted:
     • If node.left is not null, it is a root of a new tree. Add it to the global result list.
     • If node.right is not null, it is a root of a new tree. Add it to the global result list.
     • Return null (telling the caller/parent to cut the link).
   • If not deleted:
     • Return node (telling the caller/parent to keep the link).
5. Root Handling: The original root of the entire tree has no parent to receive the return value. We must manually check the return value of the initial call. If it is not null, add the original root to the result list.

Execution Flow

Let's trace the logic with a simple tree: 1 -> [2, 3] and to_delete = [1].

1. Setup: to_delete_set = {1}, result = [].
2. Call DFS(1):
   • Call DFS(2) (Left child of 1):
     • DFS(2.left) returns null.
     • DFS(2.right) returns null.
     • Check 2: Is 2 in set? No.
     • Return 2.
   • 1.left is updated to 2.
   • Call DFS(3) (Right child of 1):
     • DFS(3.left) returns null.
     • DFS(3.right) returns null.
     • Check 3: Is 3 in set? No.
     • Return 3.
   • 1.right is updated to 3.
   • Process 1:
     • Check 1: Is 1 in set? Yes.
     • 1.left is 2 (not null). Add 2 to result. result = [2].
     • 1.right is 3 (not null). Add 3 to result. result = [2, 3].
     • Return null.
3. Final Check: The initial call DFS(1) returned null. We do not add the original root to the result.
4. Output: [2, 3].

Proof of Correctness

The correctness of this algorithm relies on the Postorder Traversal property.

• Base Case: A null node returns null, correctly signifying no tree exists there.
• Inductive Step: Assume the recursive calls correctly prune the left and right subtrees and return the new roots of those subtrees (or null if deleted).
  • We assign these return values to node.left and node.right. This guarantees the current node points to the correct, updated children.
  • If the current node is deleted, we identify its non-null children as new roots (orphans) and add them to the result. By returning null, we ensure the parent of the current node (if it exists) removes the reference to this deleted node.
  • If the current node is not deleted, we return the node itself, maintaining the tree structure.
• Since we process every node exactly once and handle all structural updates via return values, the final result contains exactly the roots of the disjoint trees.

Pattern Reuse Notes

The Tree DFS - Recursive Postorder Traversal pattern is highly versatile. It is used whenever a node's value or status depends on the aggregate results of its subtrees.

• LeetCode 104: Maximum Depth of Binary Tree - We calculate the max depth of left and right subtrees before adding 1 for the current node.
• LeetCode 110: Balanced Binary Tree - We check the height balance of children before determining if the current node is balanced.
• LeetCode 124: Binary Tree Maximum Path Sum - We compute the max path sums of children before deciding how to extend the path through the current node.
• LeetCode 145: Binary Tree Postorder Traversal - The fundamental implementation of this traversal order.

Reference Implementation

C++ Solution for LeetCode 1110

1class Solution {
2public:
3    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
4        unordered_set<int> toDeleteSet(to_delete.begin(), to_delete.end());
5        vector<TreeNode*> forest;
6        
7        root = processNode(root, toDeleteSet, forest);
8        
9        // If the original root was not deleted, add it to the forest
10        if (root != nullptr) {
11            forest.push_back(root);
12        }
13        
14        return forest;
15    }
16
17private:
18    TreeNode* processNode(TreeNode* node, unordered_set<int>& toDeleteSet, vector<TreeNode*>& forest) {
19        if (node == nullptr) {
20            return nullptr;
21        }
22        
23        // Postorder traversal: process children first
24        node->left = processNode(node->left, toDeleteSet, forest);
25        node->right = processNode(node->right, toDeleteSet, forest);
26        
27        // Process current node
28        if (toDeleteSet.count(node->val)) {
29            // If current node is deleted, its children become new roots
30            if (node->left != nullptr) {
31                forest.push_back(node->left);
32            }
33            if (node->right != nullptr) {
34                forest.push_back(node->right);
35            }
36            // Return null to disconnect from parent
37            return nullptr;
38        }
39        
40        // Return node to keep connection with parent
41        return node;
42    }
43};

Java Solution for LeetCode 1110

1class Solution {
2    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
3        Set<Integer> toDeleteSet = new HashSet<>();
4        for (int val : to_delete) {
5            toDeleteSet.add(val);
6        }
7        
8        List<TreeNode> forest = new ArrayList<>();
9        
10        root = processNode(root, toDeleteSet, forest);
11        
12        // If the original root remains, add it to the forest
13        if (root != null) {
14            forest.add(root);
15        }
16        
17        return forest;
18    }
19    
20    private TreeNode processNode(TreeNode node, Set<Integer> toDeleteSet, List<TreeNode> forest) {
21        if (node == null) {
22            return null;
23        }
24        
25        // Postorder: update children first
26        node.left = processNode(node.left, toDeleteSet, forest);
27        node.right = processNode(node.right, toDeleteSet, forest);
28        
29        if (toDeleteSet.contains(node.val)) {
30            // If node is deleted, non-null children are new roots
31            if (node.left != null) {
32                forest.add(node.left);
33            }
34            if (node.right != null) {
35                forest.add(node.right);
36            }
37            // Return null to parent to sever the link
38            return null;
39        }
40        
41        return node;
42    }
43}

Python Solution for LeetCode 1110

1class Solution:
2    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
3        to_delete_set = set(to_delete)
4        forest = []
5        
6        def process_node(node):
7            if not node:
8                return None
9            
10            # Postorder traversal: update children first
11            node.left = process_node(node.left)
12            node.right = process_node(node.right)
13            
14            if node.val in to_delete_set:
15                # If current node is deleted, children become roots
16                if node.left:
17                    forest.append(node.left)
18                if node.right:
19                    forest.append(node.right)
20                # Return None to parent to break the link
21                return None
22            
23            return node
24            
25        root = process_node(root)
26        
27        # If the original root was not deleted, add it
28        if root:
29            forest.append(root)
30            
31        return forest