The O(n) Club: Delete Nodes and Return Forest – Chainsaw Edition

The O(n) Club: Delete Nodes and Return Forest – Chainsaw Edition

⚡ TL;DR

Delete designated nodes from your binary tree, then collect the roots of every resulting orphaned subtree. Post-order DFS is the magic sauce. Don’t overthink the brute force:

// Don't do this!
for (int val : to_delete) {
    // Try to delete, spend hours hunting pointers
}
// That's not how you make a forest. That's how you make a mess.

🧠 How Devs Usually Mess This Up

Some folks delete nodes up front, then realize—orphaned children are stuck clinging desperately to their old parents like interns refused severance. Common fails:

• Ditching nodes, but forgetting to hoist their children as shiny new roots.
• Returning only one tree—uh, you were supposed to return all the floating top-level trees. Plural, buddy.
• Using a List for to_delete. Brutally slow. Set it and forget it—literally, use a Set.
• Trying pre-order DFS. If you delete mom before the kids, you won’t know who survives. Drama.

🔍 What’s Actually Going On

Think of your tree as a dysfunctional company. Certain managers (nodes) are marked for “career reassignment.” When you fire one, any non-fired direct report gets promoted to branch/department head immediately. Traverse children before the parent (post-order!) so you can rescue survivors before dropping the axe on the higher-ups. Emotional damage: minimal.

🛠️ PseudoCode

• Put all to_delete values in a Set so checking is lightning fast.
  

  Set<Integer> toDeleteSet = new HashSet<>(Arrays.asList(to_delete));

• DFS from the root, passing down isRoot flag: If current node is chopped, its children become roots.
  

  TreeNode dfs(node, isRoot):
    if node == null: return null
    node.left = dfs(node.left, node should be deleted)
    node.right = dfs(node.right, node should be deleted)
    if node in toDelete:
      add node.left/right to forest if not null
      return null
    if isRoot: add node to forest
    return node

• Remember: root is a special snowflake. It might be deleted. Handle appropriately.
• Return the forest—you did collect all the roots, right?

💻 The Code

class Solution {
    public List
<treenode> delNodes(TreeNode root, int[] to_delete) {
        Set<Integer> toDeleteSet = new HashSet<>();
        for (int val : to_delete) toDeleteSet.add(val);
        List<TreeNode> res = new ArrayList<>();
        dfs(root, true, toDeleteSet, res);
        return res;
    }
    private TreeNode dfs(TreeNode node, boolean isRoot, Set<Integer> toDeleteSet, List<TreeNode> res) {
        if (node == null) return null;
        boolean deleted = toDeleteSet.contains(node.val);
        node.left = dfs(node.left, deleted, toDeleteSet, res);
        node.right = dfs(node.right, deleted, toDeleteSet, res);
        if (deleted) {
            if (node.left != null) res.add(node.left);
            if (node.right != null) res.add(node.right);
            return null;
        }
        if (isRoot) res.add(node);
        return node;
    }
}
</treenode>

⚠️ Pitfalls, Traps & Runtime Smacks

• The root could be slated for deletion. Don’t forget to check or your forest will be missing a tree trunk.
• Orphaned subtrees do NOT magically appear in your answer. You have to add them manually when a parent is deleted.
• Passing around to_delete as a List gives you O(d) nightmares. Use a Set for silent, instant lookups.
• Runtime? O(n), space O(n + d). Acceptable even for those mythical “billion-node” taxonomies interviewers love.

🧠 Interviewer Brain-Tattoo

“If you delete a binary tree node in pre-order, you’re asking for trouble. Post-order, and you get a forest. Drama-free.”