⚡Flashcard Drill➔
NeetCode #464LC-1110MediumTrees
← Back to All Problems

#464 · #1110 · Delete Nodes And Return Forest(删点成林)

📌 Problem Statement & Constraints

Given the root of a binary tree and an array to_delete of values to remove, delete those nodes and return the roots of the resulting forest. Constraints: the number of nodes is in [1, 1000], 1 <= Node.val <= 1000; values are distinct.

💡 Core Algorithmic Approaches

  1. A node becomes a new forest root when its parent was deleted (or it is the original root) and it is not itself deleted.
  2. So a DFS carries a flag indicating whether the parent was deleted.
  3. When a node is deleted, return None so the parent relinks correctly, and recurse into its children with is_root = True.
  4. The deleted node is not added to the result even if is_root is true.

💻 Benchmark Python3 Implementation

class Solution:
    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
        to_del = set(to_delete)
        res = []

        def dfs(node: Optional[TreeNode], is_root: bool) -> Optional[TreeNode]:
            if not node:
                return None
            deleted = node.val in to_del
            if is_root and not deleted:
                res.append(node)           # a new tree root
            # children of a deleted node start their own trees
            node.left = dfs(node.left, deleted)
            node.right = dfs(node.right, deleted)
            return None if deleted else node

        dfs(root, True)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(n) for the deletion set plus O(h) for the recursion.

⚠️ Interview Pitfalls & Follow-ups

  • Adding a deleted node to the result: the not deleted condition is required.
  • Passing the parent's deletion status incorrectly: is_root for a child is exactly whether its parent was deleted.
  • Forgetting to return None for deleted nodes: the parent would keep pointing at a removed subtree.
  • Using a list for to_delete: membership becomes O(k) per node, giving O(n * k); a set makes it O(1).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems