Delete Nodes And Return Forest (LeetCode 1110)
A binary tree is given by its root. Every node holds a different value. A list to_delete holds values. Delete every node whose value is in to_delete.
A node that is deleted takes its links with it. Its children are not deleted, but they have no parent now, so each of them is the top of a separate tree. After all deletions, the nodes that remain form several separate trees. This group of trees is called a forest. Return the root of every tree in the forest, in any order.
Worked Examples
root = [1,2,3,4,5,6,7], to_delete = [3,5][[1,2,null,4],[6],[7]]root = [1,2,4,null,3], to_delete = [3][[1,2,4]]⚖️Formal Constraints & Bounds
The number of nodes in the given tree is at most
1000.Each node has a distinct value between
1and1000.to_delete.length <= 1000to_deletecontains distinct values between1and1000.
Core Insight
Each call returns the node that stays in its place, and that is None for a deleted node. The parent stores the return value, so a deleted node disappears from the tree. The children of a deleted node that stay have lost their parent, so each of them is the root of a new tree.
Real-World Scenario & Production Applications
A company chart shows each manager with the people who report to them. When some managers leave, each person who reported to a leaving manager has no manager above them, and becomes the top of a separate group. A program that updates the chart must remove the right links and list every new top.
Step-by-Step Execution Trace Table
Example 1, root = [1,2,3,4,5,6,7], to_delete = [3,5], so doomed = {3, 5}. The calls finish in postorder (children before their parent):
| Step | Call | Is it deleted? | What it does | Returns | forest after |
|---|---|---|---|---|---|
| 1 | rewire(4) | no | Both children are None. | node 4 | [] |
| 2 | rewire(5) | yes | No children to send to forest. | None | [] |
| 3 | rewire(2) | no | 2.left = 4, 2.right = None (the stored return value). | node 2 | [] |
| 4 | rewire(6) | no | Both children are None. | node 6 | [] |
| 5 | rewire(7) | no | Both children are None. | node 7 | [] |
| 6 | rewire(3) | yes | Its children 6 and 7 lost their parent: both go to forest. | None | [6, 7] |
| 7 | rewire(1) | no | 1.left = 2, 1.right = None. | node 1 | [6, 7] |
| 8 | delNodes | root = rewire(root) is node 1, so it is added. | [6, 7, 1] |
The three roots are 6, 7 and 1, and the tree under node 1 is [1,2,null,4]. In step 7, 1.right = None is the line that removes node 3 from node 1. Without the assignment, node 1 would still point at node 3.
root = [1,2,3,4,5,6,7], to_delete = [3,5][[1,2,null,4],[6],[7]]Example 1, root = [1,2,3,4,5,6,7], to_delete = [3,5], so doomed = {3, 5}. The calls finish in postorder (children before their parent):
| Step | Call | Is it deleted? | What it does | Returns | forest after |
|---|---|---|---|---|---|
| 1 | rewire(4) | no | Both children are None. | node 4 | [] |
| 2 | rewire(5) | yes | No children to send to forest. | None | [] |
| 3 | rewire(2) | no | 2.left = 4, 2.right = None (the stored return value). | node 2 | [] |
| 4 | rewire(6) | no | Both children are None. | node 6 | [] |
| 5 | rewire(7) | no | Both children are None. | node 7 | [] |
| 6 | rewire(3) | yes | Its children 6 and 7 lost their parent: both go to forest. | None | [6, 7] |
| 7 | rewire(1) | no | 1.left = 2, 1.right = None. | node 1 | [6, 7] |
| 8 | delNodes | root = rewire(root) is node 1, so it is added. | [6, 7, 1] |
The three roots are 6, 7 and 1, and the tree under node 1 is [1,2,null,4]. In step 7, 1.right = None is the line that removes node 3 from node 1. Without the assignment, node 1 would still point at node 3.
| 1 | `rewire(node)` returns the node that stays in that place, or `None`, and the parent stores it: `node.left = rewire(node.left)`, `node.right = rewire(node.right)`. |
| 2 | Rewire both children first, then judge the node. A node that stays returns itself. |
| 3 | A deleted node returns `None` and sends each child that exists to `forest`, because those children lost their parent. The root keeps itself: `root = rewire(root)`, then `forest.append(root)` if it exists. |
| 4 | The trap: calling `rewire(node.left)` without storing the result. On `[1,2,4,null,3]` with `to_delete = [3]`, node 3 stays attached and the answer is `[1,2,4,null,3]` instead of `[1,2,4]`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A tree stores each child as a pointer in its parent. To delete a node, the parent's pointer must stop pointing at it. A function that only looks at the tree cannot do that. A function that returns a node can: let rewire(node) return the node that stays in that place, which is None when the node is deleted, and let the parent store the answer with node.left = rewire(node.left). The two children are rewired first, so this is a postorder walk: a node is judged after everything below it is final.
📚 The Analogy: An Organisation Chart
A company chart shows each manager with the people who report to them. When some managers leave, each person who reported to a leaving manager has no manager above them. That person becomes the top of a separate group. The chart is no longer one tree, but several. To update the chart, you go through it from the bottom: first fix the people at the lowest level, then their managers. When a manager leaves, you note down each person who reported to them and stays, because each one now leads a group of their own.
🔑 Why It Works
rewire(node) runs after both children are final, so node.left and node.right are exactly the children that stay. A node that is not deleted returns itself. A node that is deleted returns None, and its remaining children, which have lost their parent, go to forest. The root has no parent to store the answer, so delNodes keeps the root itself: root = rewire(root), then forest.append(root) if it is not None. Every node is handled once, so the work is O(N), plus O(M) to build the set of deleted values.
Calling
rewire(node.left)andrewire(node.right)without storing the resultsNot adding the root when
rewire(root)returns a nodeAdding a child of a deleted node without checking that it exists
Testing
node.val in to_deletewith the list instead of a set
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Remove every node whose value is listed in to_delete" and "give back the root of each tree that is left" say two things. Nodes disappear from the tree, and the pieces that lose their parent become roots. A tree that changes shape under a deletion rule is Rewire Tree: each call returns the node that stays in its place.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
rewire(node) returns node when it stays and None when it is deleted. Before node is checked, both children were rewired, so node.left and node.right are the nodes that stay below it. A deleted node adds those children to forest, because they have lost their parent.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap:
node.left = rewire(node.left)must store the result. Written asrewire(node.left)alone, a deleted child stays attached:[1,2,4,null,3]withto_delete = [3]returns[[1,2,4,null,3]]instead of[[1,2,4]].root = rewire(root)andif root: forest.append(root): the root has no parent to add it. Without these lines,[1,2,3]withto_delete = [3]returns[]instead of[[1,2]].if node.left:beforeforest.append(node.left): a deleted node can have one child. Without the test,Noneentersforest.doomed = set(to_delete): with the list, every test reads up to M values, and the walk costs O(N * M) instead of O(N + M).
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Rewire Tree. To delete a node, its parent must stop pointing at it. So I write a helper
rewire(node)that returns the node that stays in that place, which isNonewhen the node is deleted. The parent stores the answer:node.left = rewire(node.left). I rewire both children first, which is postorder. Then, if the node is not deleted, I return it. If it is deleted, its children that stay have lost their parent, so I add each one to the forest and returnNone. The root has no parent to store the answer, so at the end I add it to the forest ifrewire(root)returned a node. The trap is callingrewirewithout storing the result. I keep the deleted values in a set. Each node is visited once, so time is order N plus M, and space is order H for the recursion plus M for the set.
Complexity & Mathematical Proof
O(N + M)
Look at the code: rewire(node) makes one call for each child, so every node, and every empty place below a leaf, gets exactly one call. Inside a call, node.val not in doomed is a lookup in a set, which is O(1), and each forest.append is O(1). Building doomed from to_delete costs O(M). Total: O(N + M).
O(H + M)
The recursion goes one call deeper for each level of the tree, so at most H calls wait on the stack, where H is the height. doomed holds up to M values. The forest list holds the roots of the answer, which is output and is not counted.
Derivation Progression
M insertions
doomed = set(to_delete) inserts each deleted value once.
N calls that do work, N + 1 empty places
rewire is called once for each node and once for each missing child; a missing child returns at once.
O(1)
Two assignments, one set lookup and at most two appends.
O(N + M)
Each node is handled once, plus the cost of building the set.
Variable Definitions
Number of nodes in the tree (at most 1000 here)
Length of to_delete (at most 1000 here)
Height of the tree: about log N when balanced, up to N on a chain
Memory Architecture & Bounds
O(H): one call waits for each level of the tree
O(M): the set doomed
O(N): the roots in forest (not counted); the trees themselves are the input nodes, reused
Boundary Best / Worst Cases
: every node is visited, whatever the shape
time and stack on a balanced tree
time; the stack grows to on a chain
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "remove the nodes listed in to_delete", "give back the root of every tree that is left". A tree is cut by a rule and the pieces are returned: Rewire Tree, where each call returns the node that stays in its place and the parent stores it.
nodes and to_delete.length , with all values distinct in . One walk is time, plus to build the set. A chain of 1000 nodes needs about 1000 nested calls, which reaches CPython's default recursion limit of 1000: raise the limit, or use an explicit stack.
Calling rewire without storing the result leaves deleted nodes attached, and the tree keeps values that should be gone. The recursion depth equals the height of the tree, so a tree of nodes in one chain needs an explicit stack. A forest that other code reads while the walk runs may show a half-changed tree, so the walk must finish before the result is used.
Delete Nodes And Return Forest (LeetCode 1110)
A binary tree is given by its root. Every node holds a different value. A list to_delete holds values. Delete every node whose value is in to_delete.
A node that is deleted takes its links with it. Its children are not deleted, but they have no parent now, so each of them is the top of a separate tree. After all deletions, the nodes that remain form several separate trees. This group of trees is called a forest. Return the root of every tree in the forest, in any order.
Worked Examples
root = [1,2,3,4,5,6,7], to_delete = [3,5][[1,2,null,4],[6],[7]]root = [1,2,4,null,3], to_delete = [3][[1,2,4]]⚖️Formal Constraints & Bounds
The number of nodes in the given tree is at most
1000.Each node has a distinct value between
1and1000.to_delete.length <= 1000to_deletecontains distinct values between1and1000.
Core Insight
Each call returns the node that stays in its place, and that is None for a deleted node. The parent stores the return value, so a deleted node disappears from the tree. The children of a deleted node that stay have lost their parent, so each of them is the root of a new tree.
Real-World Scenario & Production Applications
A company chart shows each manager with the people who report to them. When some managers leave, each person who reported to a leaving manager has no manager above them, and becomes the top of a separate group. A program that updates the chart must remove the right links and list every new top.
Step-by-Step Execution Trace Table
Example 1, root = [1,2,3,4,5,6,7], to_delete = [3,5], so doomed = {3, 5}. The calls finish in postorder (children before their parent):
| Step | Call | Is it deleted? | What it does | Returns | forest after |
|---|---|---|---|---|---|
| 1 | rewire(4) | no | Both children are None. | node 4 | [] |
| 2 | rewire(5) | yes | No children to send to forest. | None | [] |
| 3 | rewire(2) | no | 2.left = 4, 2.right = None (the stored return value). | node 2 | [] |
| 4 | rewire(6) | no | Both children are None. | node 6 | [] |
| 5 | rewire(7) | no | Both children are None. | node 7 | [] |
| 6 | rewire(3) | yes | Its children 6 and 7 lost their parent: both go to forest. | None | [6, 7] |
| 7 | rewire(1) | no | 1.left = 2, 1.right = None. | node 1 | [6, 7] |
| 8 | delNodes | root = rewire(root) is node 1, so it is added. | [6, 7, 1] |
The three roots are 6, 7 and 1, and the tree under node 1 is [1,2,null,4]. In step 7, 1.right = None is the line that removes node 3 from node 1. Without the assignment, node 1 would still point at node 3.
root = [1,2,3,4,5,6,7], to_delete = [3,5][[1,2,null,4],[6],[7]]Example 1, root = [1,2,3,4,5,6,7], to_delete = [3,5], so doomed = {3, 5}. The calls finish in postorder (children before their parent):
| Step | Call | Is it deleted? | What it does | Returns | forest after |
|---|---|---|---|---|---|
| 1 | rewire(4) | no | Both children are None. | node 4 | [] |
| 2 | rewire(5) | yes | No children to send to forest. | None | [] |
| 3 | rewire(2) | no | 2.left = 4, 2.right = None (the stored return value). | node 2 | [] |
| 4 | rewire(6) | no | Both children are None. | node 6 | [] |
| 5 | rewire(7) | no | Both children are None. | node 7 | [] |
| 6 | rewire(3) | yes | Its children 6 and 7 lost their parent: both go to forest. | None | [6, 7] |
| 7 | rewire(1) | no | 1.left = 2, 1.right = None. | node 1 | [6, 7] |
| 8 | delNodes | root = rewire(root) is node 1, so it is added. | [6, 7, 1] |
The three roots are 6, 7 and 1, and the tree under node 1 is [1,2,null,4]. In step 7, 1.right = None is the line that removes node 3 from node 1. Without the assignment, node 1 would still point at node 3.
| 1 | `rewire(node)` returns the node that stays in that place, or `None`, and the parent stores it: `node.left = rewire(node.left)`, `node.right = rewire(node.right)`. |
| 2 | Rewire both children first, then judge the node. A node that stays returns itself. |
| 3 | A deleted node returns `None` and sends each child that exists to `forest`, because those children lost their parent. The root keeps itself: `root = rewire(root)`, then `forest.append(root)` if it exists. |
| 4 | The trap: calling `rewire(node.left)` without storing the result. On `[1,2,4,null,3]` with `to_delete = [3]`, node 3 stays attached and the answer is `[1,2,4,null,3]` instead of `[1,2,4]`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A tree stores each child as a pointer in its parent. To delete a node, the parent's pointer must stop pointing at it. A function that only looks at the tree cannot do that. A function that returns a node can: let rewire(node) return the node that stays in that place, which is None when the node is deleted, and let the parent store the answer with node.left = rewire(node.left). The two children are rewired first, so this is a postorder walk: a node is judged after everything below it is final.
📚 The Analogy: An Organisation Chart
A company chart shows each manager with the people who report to them. When some managers leave, each person who reported to a leaving manager has no manager above them. That person becomes the top of a separate group. The chart is no longer one tree, but several. To update the chart, you go through it from the bottom: first fix the people at the lowest level, then their managers. When a manager leaves, you note down each person who reported to them and stays, because each one now leads a group of their own.
🔑 Why It Works
rewire(node) runs after both children are final, so node.left and node.right are exactly the children that stay. A node that is not deleted returns itself. A node that is deleted returns None, and its remaining children, which have lost their parent, go to forest. The root has no parent to store the answer, so delNodes keeps the root itself: root = rewire(root), then forest.append(root) if it is not None. Every node is handled once, so the work is O(N), plus O(M) to build the set of deleted values.
Calling
rewire(node.left)andrewire(node.right)without storing the resultsNot adding the root when
rewire(root)returns a nodeAdding a child of a deleted node without checking that it exists
Testing
node.val in to_deletewith the list instead of a set
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Remove every node whose value is listed in to_delete" and "give back the root of each tree that is left" say two things. Nodes disappear from the tree, and the pieces that lose their parent become roots. A tree that changes shape under a deletion rule is Rewire Tree: each call returns the node that stays in its place.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
rewire(node) returns node when it stays and None when it is deleted. Before node is checked, both children were rewired, so node.left and node.right are the nodes that stay below it. A deleted node adds those children to forest, because they have lost their parent.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap:
node.left = rewire(node.left)must store the result. Written asrewire(node.left)alone, a deleted child stays attached:[1,2,4,null,3]withto_delete = [3]returns[[1,2,4,null,3]]instead of[[1,2,4]].root = rewire(root)andif root: forest.append(root): the root has no parent to add it. Without these lines,[1,2,3]withto_delete = [3]returns[]instead of[[1,2]].if node.left:beforeforest.append(node.left): a deleted node can have one child. Without the test,Noneentersforest.doomed = set(to_delete): with the list, every test reads up to M values, and the walk costs O(N * M) instead of O(N + M).
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Rewire Tree. To delete a node, its parent must stop pointing at it. So I write a helper
rewire(node)that returns the node that stays in that place, which isNonewhen the node is deleted. The parent stores the answer:node.left = rewire(node.left). I rewire both children first, which is postorder. Then, if the node is not deleted, I return it. If it is deleted, its children that stay have lost their parent, so I add each one to the forest and returnNone. The root has no parent to store the answer, so at the end I add it to the forest ifrewire(root)returned a node. The trap is callingrewirewithout storing the result. I keep the deleted values in a set. Each node is visited once, so time is order N plus M, and space is order H for the recursion plus M for the set.
Complexity & Mathematical Proof
O(N + M)
Look at the code: rewire(node) makes one call for each child, so every node, and every empty place below a leaf, gets exactly one call. Inside a call, node.val not in doomed is a lookup in a set, which is O(1), and each forest.append is O(1). Building doomed from to_delete costs O(M). Total: O(N + M).
O(H + M)
The recursion goes one call deeper for each level of the tree, so at most H calls wait on the stack, where H is the height. doomed holds up to M values. The forest list holds the roots of the answer, which is output and is not counted.
Derivation Progression
M insertions
doomed = set(to_delete) inserts each deleted value once.
N calls that do work, N + 1 empty places
rewire is called once for each node and once for each missing child; a missing child returns at once.
O(1)
Two assignments, one set lookup and at most two appends.
O(N + M)
Each node is handled once, plus the cost of building the set.
Variable Definitions
Number of nodes in the tree (at most 1000 here)
Length of to_delete (at most 1000 here)
Height of the tree: about log N when balanced, up to N on a chain
Memory Architecture & Bounds
O(H): one call waits for each level of the tree
O(M): the set doomed
O(N): the roots in forest (not counted); the trees themselves are the input nodes, reused
Boundary Best / Worst Cases
: every node is visited, whatever the shape
time and stack on a balanced tree
time; the stack grows to on a chain
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "remove the nodes listed in to_delete", "give back the root of every tree that is left". A tree is cut by a rule and the pieces are returned: Rewire Tree, where each call returns the node that stays in its place and the parent stores it.
nodes and to_delete.length , with all values distinct in . One walk is time, plus to build the set. A chain of 1000 nodes needs about 1000 nested calls, which reaches CPython's default recursion limit of 1000: raise the limit, or use an explicit stack.
Calling rewire without storing the result leaves deleted nodes attached, and the tree keeps values that should be gone. The recursion depth equals the height of the tree, so a tree of nodes in one chain needs an explicit stack. A forest that other code reads while the walk runs may show a half-changed tree, so the walk must finish before the result is used.