How do you solve Delete Nodes And Return Forest on LeetCode?

Delete Nodes And Return Forest (LeetCode #1110) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a set for to_delete allows for O(1) lookups, making the algorithm efficient.

What is the brute force solution for Delete Nodes And Return Forest?

The brute force approach for Delete Nodes And Return Forest is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute-force approach, we traverse the entire tree and check if each node's value is in the to_delete list. If it is, we remove that node and its children. This approach is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Delete Nodes And Return Forest?

Always clarify the problem constraints and edge cases with the interviewer. Discuss your thought process and approach before jumping into coding. Test your code with different scenarios to ensure correctness.

What are common mistakes when solving Delete Nodes And Return Forest?

Not using a set for to_delete, leading to O(n) lookups instead of O(1). Forgetting to check if a node is a root before adding it to the result.

#1110

Delete Nodes And Return Forest

Medium

ArrayHash TableTreeDepth-First SearchBinary TreeHash MapTree Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution also uses DFS but efficiently manages the deletion process by leveraging a set for quick lookups. It avoids unnecessary traversals by directly returning null for deleted nodes, ensuring we only traverse each node once.

⚙️

Algorithm

4 steps

1Step 1: Convert the to_delete list into a set for O(1) lookups.
2Step 2: Perform a DFS on the tree, checking if each node should be deleted.
3Step 3: If a node is not deleted and is a root, add it to the result list.
4Step 4: Recursively process left and right children, returning null for deleted nodes.

solution.py23 lines

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7class Solution:
8    def delNodes(self, root, to_delete):
9        to_delete_set = set(to_delete)
10        result = []
11
12        def dfs(node, is_root):
13            if not node:
14                return None
15            root_deleted = node.val in to_delete_set
16            if is_root and not root_deleted:
17                result.append(node)
18            node.left = dfs(node.left, root_deleted)
19            node.right = dfs(node.right, root_deleted)
20            return None if root_deleted else node
21
22        dfs(root, True)
23        return result

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once. The space complexity is O(n) due to the storage of the result list and the set for to_delete.

1Using a set for to_delete allows for O(1) lookups, making the algorithm efficient.
2Recursive DFS helps in managing the tree structure and deletion in a clean manner.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.