#1110

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Delete Nodes And Return Forest

Delete nodes from a binary tree using array scanning and hash lookup to return the remaining forest efficiently.

array hash table tree depth first search binary tree

Problem Statement

You are given the root of a binary tree where each node has a unique value. Given a list of values to delete, remove all nodes matching any value in the list.

After deletions, multiple disconnected trees may remain. Return the roots of all remaining trees as a list, representing the forest formed by removing the specified nodes. The order of trees in the output does not matter.

Examples

Example 1

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

Output: [[1,2,null,4],[6],[7]]

Example details omitted.

Example 2

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

Output: [[1,2,4]]

Example details omitted.

Constraints

The number of nodes in the given tree is at most 1000.
Each node has a distinct value between 1 and 1000.
to_delete.length <= 1000
to_delete contains distinct values between 1 and 1000.

Solution Approach

Hash set for deletion lookup

Store all values to delete in a hash set for O(1) access. This ensures that each node can be checked quickly during traversal, preventing unnecessary repeated scans.

Recursive DFS traversal

Perform a depth-first search from the root. If a node is in the delete set, recursively process its children and add non-deleted ones to the forest. Return null for deleted nodes to disconnect them from their parent.

Forest collection and result formation

Whenever a non-deleted node has no parent (root or child of a deleted node), add it to the forest list. Collecting roots during traversal avoids an extra pass and ensures all trees in the forest are captured.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) because each node is visited once. Space complexity is O(n) for the hash set storing nodes to delete and for recursion stack in the worst case of a skewed tree.

What Interviewers Usually Probe

Asks about handling child nodes of deleted parents.
Probes if the hash set lookup is necessary for efficiency.
Questions how to maintain forest roots without extra passes.

Common Pitfalls or Variants

Common pitfalls

Forgetting to add child nodes of deleted nodes to the forest.
Modifying the tree incorrectly, losing subtrees during deletion.
Using repeated linear scans instead of a hash set, causing O(n^2) behavior.

Follow-up variants

Delete nodes with values in a given range instead of an explicit list.
Return the forest in a specific order, such as preorder traversal of roots.
Handle trees where duplicate values may exist, requiring careful identification.

FAQ

What is the most efficient way to track nodes to delete in Delete Nodes And Return Forest?

Use a hash set for all to_delete values to allow constant-time lookup during DFS traversal.

How do I handle child nodes of a deleted parent?

Add each non-deleted child to the forest list when their parent is removed to maintain the correct forest structure.

Can I solve this without recursion?

Yes, iterative DFS or BFS with a stack or queue is possible, but recursion simplifies handling child connections and forest collection.

What is the time complexity of this approach?

O(n) because each node is visited once and each hash set lookup is O(1).

Why is array scanning plus hash lookup important here?

It ensures fast identification of nodes to delete and prevents losing children in the forest, avoiding inefficient repeated tree scans.

terminal

Solution

Solution 1: DFS

First, we use a hash table or an array of length 1001, `s`, to record all nodes that need to be deleted.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

# 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]:
        def dfs(root: Optional[TreeNode]) -> Optional[TreeNode]:
            if root is None:
                return None
            root.left, root.right = dfs(root.left), dfs(root.right)
            if root.val not in s:
                return root
            if root.left:
                ans.append(root.left)
            if root.right:
                ans.append(root.right)
            return None

        s = set(to_delete)
        ans = []
        if dfs(root):
            ans.append(root)
        return ans

Solution 2: BFS

#### TypeScript

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

# 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]:
        def dfs(root: Optional[TreeNode]) -> Optional[TreeNode]:
            if root is None:
                return None
            root.left, root.right = dfs(root.left), dfs(root.right)
            if root.val not in s:
                return root
            if root.left:
                ans.append(root.left)
            if root.right:
                ans.append(root.right)
            return None

        s = set(to_delete)
        ans = []
        if dfs(root):
            ans.append(root)
        return ans

Continue Practicing

#1123 lowest common ancestor of deepest leaves #987 vertical order traversal of a binary tree #1261 find elements in a contaminated binary tree