1110. Delete Nodes And Return Forest
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.
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_deletelist into a set for a faster lookup. - Use a helper function
dfsto 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_deleteset, 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.
What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?
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_deleteto 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 listto_deleteis converted to a setsat the beginning of the function. -
Depth-First Search (DFS) Function: The
dfsfunction 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 returnsNone. This base case helps to end the recursion. - It calls itself on the
leftandrightchildren 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.
- It first checks if the current node 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
Noneto indicate that the current node should be removed from the tree.
- Before deletion, it checks if the left child exists and then appends it to the answer list
-
Finalizing the Answer: Finally, after calling
dfson the root, if the root is not part ofto_deleteand the resulting subtree still has the root node, the root is added to theanslist.- This check is necessary because the root might not have a parent to check it and add its children to the
anslist if it were to be deleted. Since thedfsfunction only adds the children of a deleted node to theanslist, if the root is not deleted, it must independently be added to the list of roots in the resulting forest.
- This check is necessary because the root might not have a parent to check it and add its children to the
-
Returning the Forest: The
anslist 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.
Which of the following shows the order of node visit in a Breadth-first Search?
Example Walkthrough
Initial Binary Tree Setup
Imagine a binary tree with the following structure:
1 1 2 / \ 3 2 3 4 / / \ 5 4 5 6 6 / 7 7
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 ins, 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 returnNone, effectively deleting it from its parent (node 2). Since node 4 has no children, no new roots are added.
- Left Child of Node 2 (4): Node 4 is in set
-
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
sand becomes a new root. It's added to theanslist. -
Right Child of Node 3 (6): Node 6 is not in
sand, likewise, becomes a new root. It's added to theanslist.
After processing node 5 and node 6 as new roots, node 3 is deleted and we return
Noneto 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 theanslist. Then, node 7 is removed by returningNone.
-
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 1 5 6 2 / 32
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
401import 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}
601#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};
661// 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}
70What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?
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
scontains at mostkelements, wherekis the size of theto_deletelist, resulting in a space complexity ofO(k). - The list
anscould theoretically contain all the nodes in the case that all nodes are to be deleted, which would beO(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 beO(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.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.