1110. Delete Nodes And Return Forest

MediumTreeDepth-First SearchArrayHash TableBinary Tree

Problem Description

The given problem involves manipulating a binary tree based on certain deletion rules. We start with a binary tree where each node has a distinct value. We're given a list of values to_delete. Our task is to remove all nodes that have values contained in this list. After the deletion process, the original binary tree might be split into one or more smaller trees since deleting nodes might break connections between parent and child nodes. These separated smaller trees, when taken together, are referred to as a forest. What we need to return is a list of the root nodes for each of the trees in this resulting forest. The order of root nodes in the output list does not matter.

Flowchart Walkthrough

Let's analyze the problem using the Flowchart. Here's a step-by-step breakdown:

Is it a graph?

Yes: We can think of the tree structure in this problem as a special kind of graph.

Is it a tree?

Yes: The specific structure mentioned in the problem is a tree, where nodes represent tree nodes and edges represent direct parent-child relationships.

Following the flowchart, since it is a tree, the suggested algorithm is DFS (Depth-First Search).

Conclusion: The algorithm flowchart guides us to utilize DFS for this tree-based problem, as trees are a subtype of graphs and Depth-First Search is especially effective for tree traversals and modifications like deleting nodes.

Intuition

The primary intuition for solving this problem lies in the traversal of the binary tree and deciding whether to delete a node or not. A depth-first search (DFS) is a natural choice for this process since it allows us to visit every node and make decisions as we go, whilst also ensuring we handle the children before processing the parent (which is important because a deleted child might be a new root).

The approach is to traverse the tree, and as we do, we check each node against the values in to_delete. If a node's value is in the to_delete set, we need to remove this node. But before we remove a node, if it has children, we must ensure that these children, which will now be root nodes of their own trees, are included in our answer.

Thus, our solution's strategy is as follows:

Convert the to_delete list into a set for a faster lookup.
Use a helper function dfs to perform depth-first search starting at the root. This function will handle the logic of deletion. If a node needs to be deleted, it checks and attaches the node's children (if they exist) to the forest (list of new roots) before deleting the node itself.
If the initial root node is not part of the to_delete set, add it to the list of new roots.
Start the DFS process and return the list of new roots as the answer.

By doing so, we ensure that we create the forest in an efficient way, only touching each node once and correctly identifying each remaining tree's root nodes, without relying on the deletion order.

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

Solution Approach

The provided solution employs a recursive depth-first search (DFS) pattern to traverse the binary tree and apply the deletion logic. Here's how the solution is implemented:

Converting to_delete to a Set: Sets offer O(1) complexity for lookup operations. This is critical because we need to check whether or not to delete each node quickly. The list to_delete is converted to a set s at the beginning of the function.
Depth-First Search (DFS) Function: The dfs function is a recursive helper function that traverses the tree. It is responsible for determining whether a node needs to be deleted as well as preparing the children to be new roots if necessary.
- It first checks if the current node is None, and if so, it returns None. This base case helps to end the recursion.
- It calls itself on the left and right children of the current node so that the entire subtree rooted at the current node is processed before deciding on the deletion of the current node.
- After its left and right children are processed, it checks if the current node is not in the set s. If it isn't, it means that the current node is not to be deleted, and the node is returned as it is.
Deleting a Node: If a node is in the s, this node has to be deleted.
- Before deletion, it checks if the left child exists and then appends it to the answer list ans. The same is done for the right child. This process saves the children as the new roots in the resulting forest since their parent is being deleted.
- After handling the children, the function returns None to indicate that the current node should be removed from the tree.
Finalizing the Answer: Finally, after calling dfs on the root, if the root is not part of to_delete and the resulting subtree still has the root node, the root is added to the ans list.
- This check is necessary because the root might not have a parent to check it and add its children to the ans list if it were to be deleted. Since the dfs function only adds the children of a deleted node to the ans list, if the root is not deleted, it must independently be added to the list of roots in the resulting forest.
Returning the Forest: The ans list now contains all the roots of the trees that make up the forest after deletion operations are complete. This list is returned as the final answer to the problem.

Overall, the implementation elegantly uses recursion to break down the complex problem of tree deletion into manageable parts, adhering to the DFS traversal algorithm principles, and efficiently utilizes data structures like set and list to track which nodes to delete and to accumulate the resulting forest's roots.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Initial Binary Tree Setup

Imagine a binary tree with the following structure:

The node values are unique and there is a to_delete array with values [3,4,7].

Conversion of `to_delete` to a Set

The first step of the solution approach is converting the to_delete list to a set s. Therefore, s = {3, 4, 7}. This will allow quick checks against the nodes to decide if they should be deleted.

DFS to determine deletions and new roots

Next, we proceed with a depth-first search:

Root Node (1): Node 1 is checked against the set s. Since 1 is not in s, we proceed with the DFS on its left and right children.
Left Child of Root (2): Node 2 is also not in s. So, its left child (4) is examined in the next recursive call.
- Left Child of Node 2 (4): Node 4 is in set s, so before we delete node 4, we check if node 4 has children, which it doesn't. We then return None, effectively deleting it from its parent (node 2). Since node 4 has no children, no new roots are added.
Right Child of Root (3): Node 3 is in s, and before we delete node 3, we check its children.
- Left Child of Node 3 (5): Node 5 is not in s and becomes a new root. It's added to the ans list.
- Right Child of Node 3 (6): Node 6 is not in s and, likewise, becomes a new root. It's added to the ans list.
After processing node 5 and node 6 as new roots, node 3 is deleted and we return None to its parent (node 1).
- Left Child of Node 5 (7): Node 7 is checked. It is in set s, so before being deleted, if it had children (which it does not), those would be added to the ans list. Then, node 7 is removed by returning None.

Finalizing the Forest

After processing the DFS, we check the initial root node (1). Since it is not in s, we add it to our ans list – now containing the roots of the resulting forest: [1, 5, 6].

Final Forest

The final forest, after deletion, consists of individual trees with root nodes 1, 5, and 6, which means our ans list is correct.

The forest looks like:

  1     5     6
 /            
2

Thus, returning [1, 5, 6] as the final root nodes of trees in the forest after deletion.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
10        # Set to store the values that need to be deleted
11        to_delete_set = set(to_delete)
12        # List to accumulate the resulting forest nodes
13        forest = []
14
15        # Helper function performing a DFS on the tree
16        def dfs(node: Optional[TreeNode]) -> Optional[TreeNode]:
17            if node is None:
18                return None
19            # Recursively call on left and right children
20            node.left = dfs(node.left)
21            node.right = dfs(node.right)
22          
23            # If current node's value is in the 'to_delete' set
24            if node.val in to_delete_set:
25                # Append children to forest if they are not None
26                if node.left:
27                    forest.append(node.left)
28                if node.right:
29                    forest.append(node.right)
30                # Returning None, as this node gets deleted
31                return None
32            # If the node isn't getting deleted, return it
33            return node
34
35        # Starting the DFS from the root; if the root isn't deleted, append to forest
36        if dfs(root):
37            forest.append(root)
38      
39        return forest
40

1import java.util.ArrayList;
2import java.util.List;
3
4// TreeNode structure as defined by the problem statement.
5class TreeNode {
6    int val;
7    TreeNode left;
8    TreeNode right;
9    TreeNode() {}
10    TreeNode(int val) { this.val = val; }
11    TreeNode(int val, TreeNode left, TreeNode right) {
12        this.val = val;
13        this.left = left;
14        this.right = right;
15    }
16}
17
18class Solution {
19    // To keep track of nodes to delete using their values.
20    private boolean[] toDelete = new boolean[1001];
21    // To store the resulting forest after deletions.
22    private List<TreeNode> forest = new ArrayList<>();
23
24    // Main function to delete nodes and return the remaining forest as a list.
25    public List<TreeNode> delNodes(TreeNode root, int[] delNodes) {
26        // Populate the toDelete array to mark nodes that need to be deleted.
27        for (int value : delNodes) {
28            toDelete[value] = true;
29        }
30        // Perform a DFS and add the root to the forest if it's not deleted.
31        if (deleteAndReturnValidRoot(root) != null) {
32            forest.add(root);
33        }
34        return forest;
35    }
36
37    // Helper function to perform DFS and handle deletions.
38    private TreeNode deleteAndReturnValidRoot(TreeNode node) {
39        if (node == null) {
40            return null;
41        }
42        // Recursively deal with the left and right subtrees.
43        node.left = deleteAndReturnValidRoot(node.left);
44        node.right = deleteAndReturnValidRoot(node.right);
45        // If current node is not to be deleted, return it.
46        if (!toDelete[node.val]) {
47            return node;
48        }
49        // If this node is to be deleted, add its children to the forest.
50        if (node.left != null) {
51            forest.add(node.left);
52        }
53        if (node.right != null) {
54            forest.add(node.right);
55        }
56        // Return null because this node is to be deleted.
57        return null;
58    }
59}
60

1#include <vector>
2#include <functional> // For std::function
3#include <cstring>    // For memset
4
5// Definition for a binary tree node.
6struct TreeNode {
7    int val;
8    TreeNode *left;
9    TreeNode *right;
10    TreeNode() : val(0), left(nullptr), right(nullptr) {}
11    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
13};
14
15class Solution {
16public:
17    // Function to delete nodes from a binary tree based on a list of values and return the forest of trees.
18    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& toDelete) {
19        bool toDeleteMarker[1001]; // Create a marker array to indicate which values should be deleted.
20        memset(toDeleteMarker, 0, sizeof(toDeleteMarker)); // Initialize marker array to false.
21
22        // Fill the marker array for the values to be deleted.
23        for (int value : toDelete) {
24            toDeleteMarker[value] = true;
25        }
26
27        // Answer vector to hold the roots of trees in the resulting forest.
28        vector<TreeNode*> forest;
29
30        // Recursive depth-first search to process and delete nodes.
31        std::function<TreeNode*(TreeNode*)> dfs = [&](TreeNode* node) -> TreeNode* {
32            if (!node) {
33                return nullptr; // If the node is null, return null.
34            }
35
36            // Recursively process left and right children.
37            node->left = dfs(node->left);
38            node->right = dfs(node->right);
39
40            // If the current node's value is marked to delete
41            if (toDeleteMarker[node->val]) {
42                // If the left child exists, add it to the forest.
43                if (node->left) {
44                    forest.push_back(node->left);
45                }
46                // If the right child exists, add it to the forest.
47                if (node->right) {
48                    forest.push_back(node->right);
49                }
50                // Return null since the current node is to be deleted.
51                return nullptr;
52            }
53            // If the current node is not to be deleted, then return the node itself.
54            return node;
55        };
56
57        // Root of the processed tree. If it's not null, add it to the forest.
58        if (TreeNode* remainingRoot = dfs(root)) {
59            forest.push_back(remainingRoot);
60        }
61
62        // Return the forest of trees after deletions have been performed.
63        return forest;
64    }
65};
66

1// Definition for a binary tree node.
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6  
7    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8        this.val = (val === undefined ? 0 : val);
9        this.left = (left === undefined ? null : left);
10        this.right = (right === undefined ? null : right);
11    }
12}
13
14/**
15 * Delete nodes from a binary tree given a list of values to delete. Return
16 * the resulting forest as an array of tree roots.
17 * @param {TreeNode | null} root - The root of the binary tree.
18 * @param {number[]} toDelete - The values of nodes to delete.
19 * @return {Array<TreeNode | null>} - The resulting forest after deletions.
20 */
21function delNodes(root: TreeNode | null, toDelete: number[]): Array<TreeNode | null> {
22    // Array to track whether a value should be deleted or not.
23    // Initialized as false, as true values will be assigned based on the toDelete array.
24    const toBeDeleted: boolean[] = Array(1001).fill(false);
25    // Mark the values that need to be deleted
26    for (const value of toDelete) {
27        toBeDeleted[value] = true;
28    }
29
30    // Resulting array of tree roots that form the forest after deletions.
31    const forest: Array<TreeNode | null> = [];
32
33    /**
34     * The Depth-first Search (DFS) function to traverse the tree and make deletions.
35     * @param {TreeNode | null} node - The current node being processed.
36     * @return {TreeNode | null} - The new tree with deletions, or null if node is deleted.
37     */
38    const dfs = (node: TreeNode | null): TreeNode | null => {
39        if (!node) {
40            return null;
41        }
42      
43        // Recursively apply the DFS to the left and right children.
44        node.left = dfs(node.left);
45        node.right = dfs(node.right);
46        // If the current node should not be deleted, return it as is.
47        if (!toBeDeleted[node.val]) {
48            return node;
49        }
50      
51        // If the node should be deleted and has a left child, add it to the forest array.
52        if (node.left) {
53            forest.push(node.left);
54        }
55        // If the node should be deleted and has a right child, add it to the forest array.
56        if (node.right) {
57            forest.push(node.right);
58        }
59        // Returning null indicates that the current node has been deleted.
60        return null;
61    };
62  
63    // Kick-off DFS from the root. If the root is not deleted, add it to the forest array.
64    if (dfs(root)) {
65        forest.push(root);
66    }
67
68    return forest;
69}
70

Time and Space Complexity

Time Complexity

The time complexity of the provided code is primarily driven by the depth-first search (DFS) function, which traverses each node of the binary tree exactly once. During this traversal, the function performs constant-time operations for each node, such as checking membership in s, the set of nodes to delete, and appending children of deleted nodes to ans.

Therefore, the time complexity is O(N), where N is the number of nodes in the tree, since each node is visited once.

Space Complexity

The space complexity is determined by the storage required for the recursive calls of the DFS function, the set s, and the list ans.

The set s contains at most k elements, where k is the size of the to_delete list, resulting in a space complexity of O(k).
The list ans could theoretically contain all the nodes in the case that all nodes are to be deleted, which would be O(N).
The recursive DFS function will use stack space proportional to the height of the tree. In the worst-case scenario of a skewed tree, the height could be O(N). In a balanced tree, the height would be O(log N).

Hence, the overall space complexity is O(N + k), which simplifies to O(N) if we consider k <= N, since the set and the output list's size are both bound by the number of nodes in the tree.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know