What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Depth-First Search (DFS)

Builds on Bottom-Up DFS, which you haven’t finished yet.

P3MediumBuilt on Bottom-Up DFS~3 min speedrun

Rewire Tree (Return the Node That Stays)

Built on

Bottom-Up DFSEach call returns the node that stays in its place, which may be None, and the parent stores that return value as its child.

The problem

Delete Nodes And Return Forest (LC 1110)(opens leetcode.com)

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.

Example 1

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

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

Node 3 is deleted, so its children 6 and 7 become roots of their own trees. Node 5 is deleted too, and it has no children. The tree of node 1 keeps nodes 1, 2 and 4.

Rewire Tree

tree + delete rule ➔ each call returns the node that stays (or None) ➔ parent stores it as its child

Spot it when: A rule deletes some nodes of a tree, and the answer is the changed tree or the roots of the pieces that remain. The parent must stop pointing at a deleted child.

Rewire Tree

Python

1	from typing import List, Optional
2
3	class TreeNode:
4	def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None):
5	self.val = val
6	self.left = left
7	self.right = right
8
9	def delNodes(root: Optional[TreeNode], to_delete: List[int]) -> List[Optional[TreeNode]]:
10	"""Delete Nodes And Return Forest: delete every node whose value is in to_delete and
11	return the roots of the trees that remain.
12	N = number of nodes. M = len(to_delete). H = height.
13	Time: O(N + M) \| Space: O(H + M) recursion stack and the set of deleted values, output not counted
14	"""
15	doomed = set(to_delete) # A set makes each test "is this value deleted?" O(1)
16	forest: List[Optional[TreeNode]] = [] # The root of every tree that remains
17
18	def rewire(node: Optional[TreeNode]) -> Optional[TreeNode]:
19	"""Returns the node that stays in node's place after every deletion in its
20	subtree, or None if node itself is deleted."""
21	if not node:
22	return None # An empty place stays empty
23	# 1. Rewire Both Subtrees First:
24	# Postorder: each child returns the node that stays in its place, and node
25	# stores it, so a deleted child stops being node's child.
26	node.left = rewire(node.left)
27	node.right = rewire(node.right)
28
29	# 2. Keep The Node:
30	# A node that is not deleted stays where it is, with its children already
31	# rewired.
32	if node.val not in doomed:
33	return node
34
35	# 3. Delete The Node:
36	# A deleted node loses its parent link, so each child that stays is the root of
37	# a new tree. Both children were rewired in step 1, so neither is deleted.
38	if node.left:
39	forest.append(node.left)
40	if node.right:
41	forest.append(node.right)
42	return None
43
44	# 4. Keep The Root If It Stays:
45	# The root has no parent to store the return value, so this function keeps it when
46	# rewire(root) returns a node.
47	root = rewire(root)
48	if root:
49	forest.append(root)
50	return forest

Invariant: rewire(node) returns node when it stays and None when it is deleted, and every pointer below node already points only at nodes that stay.

A deleted node must also disappear from its parent's pointer, so let rewire(node) return the node that stays in that place, or None, and let the parent store it: node.left = rewire(node.left). Both children are rewired before node is checked, so when node is deleted, node.left and node.right are already final, and each one that exists is the root of a new tree for forest. A node that is kept returns itself. The root has no parent to store the result, so delNodes appends it to forest when rewire(root) returns a node. The trap is calling rewire(node.left) without storing the result: the deleted child stays attached to its parent, and the tree still contains a value that should be gone.

See it run

Rewire Tree, step by step

call now 1returns -answer not yet

Each call returns the node that stays in its place, or None. The parent stores the return value as its child.

now the call that is running
waiting a call that waits for its children
stays a node whose call returned the node
deleted a node whose call returned None

Call rewire on the node 1. The call waits for its two children before it checks the node.

forest (roots)

empty

1 / 15

Gotchas1 of 4

The trap
Gotcha 1: Calling rewire(node.left) and rewire(node.right) without storing the results
Mistake
```
rewire(node.left)
rewire(node.right)
```
Fix
```
node.left = rewire(node.left)
node.right = rewire(node.right)
```
What happens: rewire(node.left) returns None when the left child is deleted, but the call does not change node.left. If the result is not stored, node still points at the deleted child. In [1,2,4,null,3] with to_delete = [3], node 2 still points at node 3, so the tree keeps the value 3 that should be gone.
Example: root = [1,2,4,null,3], to_delete = [3] (each tree is shown as its level-order list)
Mistake: returns [[1, 2, 4, None, 3]]Fix: returns [[1, 2, 4]]
Gotcha 2: Not adding the root when rewire(root) returns a node
Mistake
```
rewire(root)
```
Fix
```
root = rewire(root)
if root:
    forest.append(root)
```
What happens: Only a deleted node adds its children to forest. A root that stays has no deleted parent, so no other line adds it. Without the last three lines, a root that stays is missing from the answer. In [1,2,3] with to_delete = [3], node 3 is deleted and the tree [1,2] stays, but forest is empty.
Example: root = [1,2,3], to_delete = [3]
Mistake: returns []Fix: returns [[1, 2]]
Gotcha 3: Adding a child of a deleted node without checking that it exists
Mistake
```
forest.append(node.left)
forest.append(node.right)
```
Fix
```
if node.left:
    forest.append(node.left)
if node.right:
    forest.append(node.right)
```
What happens: A deleted node can have only one child, and None is not a tree. forest.append(node.right) adds None to the answer when node has no right child. In [1,2] with to_delete = [1], node 1 has no right child, so forest holds node 2 and None. The answer must hold only real roots.
Example: root = [1,2], to_delete = [1] (an empty list in the output stands for None)
Mistake: returns [[], [2]]Fix: returns [[2]]
Gotcha 4: Testing node.val in to_delete with the list instead of a set
What happens: in on a list reads the list from its start for every node. With N nodes and M values in to_delete, that costs O(N * M) instead of O(N + M). doomed = set(to_delete) makes each test O(1).

Not this one if…

The tree is a binary search tree and the rule is a range of values, as in Trim a Binary Search Tree (LC 669): the order tells you which whole side to drop without visiting it. Switch to BST Bounds. See BST Bounds
You build one tree from two input trees, as in Merge Two Binary Trees (LC 617): each call needs a pair of nodes, not one node. Switch to Two Tree Walk. See Two Tree Walk

Deep Dive

Why the parent must store what the call returns

A tree keeps each child as a pointer in its parent. To delete a node, the parent's pointer must stop pointing at it. A call that only looks at the tree cannot change that pointer. A call that returns a node can: rewire(node) returns the node that stays in that place, and it returns None when the node is deleted.

The parent stores the answer with node.left = rewire(node.left). Take the tree [1, 2, 3, 4, 5, 6, 7] with to_delete = [3, 5]. The call on the node 5 returns None, and the node 2 stores it, so the node 2 has no right child. The call on the node 3 returns None, and the node 1 stores it, so the node 1 has no right child.

Without the assignment, the node 2 would still point at the node 5 and the node 1 would still point at the node 3. The tree would keep the values that should be gone.

Why both children are rewired before the node is checked

A deleted node cannot take its children with it. Each child that stays has lost its parent, so it is the root of a new tree. The deleted node must know which of its children stay, and that is known only after the calls on the children have returned.

So the walk is postorder. In the example, the calls on the nodes 6 and 7 return both nodes. When the call on the node 3 sees that 3 is deleted, node.left is the node 6 and node.right is the node 7, and both go to forest.

A child of a deleted node can be deleted too. Because the children were rewired first, such a child already returned None, so node.left is None and it is not added. Adding the children before the calls run would add a deleted node to forest.

Delete Leaves With a Given Value: the rule reads the rewired children

Delete Leaves With a Given Value (LC 1325) uses the same walk with another rule. A node is deleted when it is a leaf that holds target. After the two assignments, a node whose children were both removed has no children, so it is a leaf now.

That is why the rule is checked after the children are rewired. On [1, 2, null, 2, null, 2] with target = 2, the deepest node is removed first. Its parent becomes a leaf with the value 2 and is removed next, and so on up the chain. The answer is [1].

Binary Tree Pruning (LC 814) works the same way: a node is removed when it holds 0 and has no children after its subtrees were pruned. Delete Node in a BST (LC 450) returns the node that replaces the deleted node, and the parent stores it.

The cost, and the root

Each node gets one call, and each missing child gets one call that returns at once. A call does a set lookup and at most two appends, so the time is O(N + M), where M is the length of to_delete. The recursion stack is as deep as the tree is high, so the space is O(H + M) with the set.

The root has no parent to store the return value. delNodes therefore writes root = rewire(root) and adds the root to forest when it is not None. Without that, a root that stays is missing from the answer.

60-Second Pitch

"To delete a node, its parent must stop pointing at it, so I write rewire(node) to return the node that stays in that place, or None. The parent stores the answer: node.left = rewire(node.left). I rewire both children first. Then a node that is not deleted returns itself, and a deleted node sends each child that stays to the forest and returns None. The root has no parent, so I add it myself when it stays. Each node is visited once, so the time is O(N + M) and the stack is as deep as the tree."

Common Questions

How is Rewire Tree different from Bottom-Up DFS?: Bottom-Up DFS returns a number or a flag that describes a subtree. Rewire Tree returns the node itself, and the parent stores it as its child, so the call changes the shape of the tree.
Why does the root need special handling?: Every other node has a parent that stores the return value. The root has none, so delNodes stores the result in root and adds it to forest if it is not None.
What happens if a deleted node has a deleted child?: The child was rewired first and returned None, so the deleted node sees None in that place and does not add it to forest.
Why use a set for to_delete?: A set lookup is O(1). A list lookup reads up to M values for every node and makes the walk O(N * M).

SWE Reasoning

Spot it

The statement deletes, removes or cuts nodes of a tree by a rule.
The answer is the changed tree, or the roots of the pieces that remain.
Whether a node is removed can depend on what is left below it after its own children were changed.
You can say in one sentence what rewire(node) returns: the node that stays in that place, or None.

The invariant, step by step

Define rewire(node) as the node that stays in node's place after every deletion in its subtree, or None.
Rewire both children and store the results. After that, no pointer below node leads to a deleted node.
If the rule keeps node, return it. If the rule removes it, each child that stays lost its parent and goes to forest, and the call returns None.
The root has no parent, so delNodes stores the result in root and adds it to forest when it exists.

Traps

Not storing the result. rewire(node.left) alone leaves a deleted child attached to its parent.
Forgetting the root. A root that stays has no deleted parent to add it to forest.
Adding a missing child. A deleted node can have one child. Test if node.left: before forest.append(node.left).
A list for the deleted values. A set makes each test O(1).

Practice

Canonical LeetCode:Delete Nodes And Return Forest (LC 1110)Binary Tree Pruning (LC 814)Delete Leaves With a Given Value (LC 1325)Delete Node in a BST (LC 450)Invert Binary Tree (LC 226)

Theory Context•Depth-First Search (DFS)

Builds on Bottom-Up DFS, which you haven’t finished yet.

P3MediumBuilt on Bottom-Up DFS~3 min speedrun

Rewire Tree (Return the Node That Stays)

Built on

Bottom-Up DFSEach call returns the node that stays in its place, which may be None, and the parent stores that return value as its child.

The problem

Delete Nodes And Return Forest (LC 1110)(opens leetcode.com)

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.

Example 1

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

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

Node 3 is deleted, so its children 6 and 7 become roots of their own trees. Node 5 is deleted too, and it has no children. The tree of node 1 keeps nodes 1, 2 and 4.

Rewire Tree

tree + delete rule ➔ each call returns the node that stays (or None) ➔ parent stores it as its child

Spot it when: A rule deletes some nodes of a tree, and the answer is the changed tree or the roots of the pieces that remain. The parent must stop pointing at a deleted child.

Rewire Tree

Python

1	from typing import List, Optional
2
3	class TreeNode:
4	def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None):
5	self.val = val
6	self.left = left
7	self.right = right
8
9	def delNodes(root: Optional[TreeNode], to_delete: List[int]) -> List[Optional[TreeNode]]:
10	"""Delete Nodes And Return Forest: delete every node whose value is in to_delete and
11	return the roots of the trees that remain.
12	N = number of nodes. M = len(to_delete). H = height.
13	Time: O(N + M) \| Space: O(H + M) recursion stack and the set of deleted values, output not counted
14	"""
15	doomed = set(to_delete) # A set makes each test "is this value deleted?" O(1)
16	forest: List[Optional[TreeNode]] = [] # The root of every tree that remains
17
18	def rewire(node: Optional[TreeNode]) -> Optional[TreeNode]:
19	"""Returns the node that stays in node's place after every deletion in its
20	subtree, or None if node itself is deleted."""
21	if not node:
22	return None # An empty place stays empty
23	# 1. Rewire Both Subtrees First:
24	# Postorder: each child returns the node that stays in its place, and node
25	# stores it, so a deleted child stops being node's child.
26	node.left = rewire(node.left)
27	node.right = rewire(node.right)
28
29	# 2. Keep The Node:
30	# A node that is not deleted stays where it is, with its children already
31	# rewired.
32	if node.val not in doomed:
33	return node
34
35	# 3. Delete The Node:
36	# A deleted node loses its parent link, so each child that stays is the root of
37	# a new tree. Both children were rewired in step 1, so neither is deleted.
38	if node.left:
39	forest.append(node.left)
40	if node.right:
41	forest.append(node.right)
42	return None
43
44	# 4. Keep The Root If It Stays:
45	# The root has no parent to store the return value, so this function keeps it when
46	# rewire(root) returns a node.
47	root = rewire(root)
48	if root:
49	forest.append(root)
50	return forest

Invariant: rewire(node) returns node when it stays and None when it is deleted, and every pointer below node already points only at nodes that stay.

See it run

Rewire Tree, step by step

call now 1returns -answer not yet

Each call returns the node that stays in its place, or None. The parent stores the return value as its child.

now the call that is running
waiting a call that waits for its children
stays a node whose call returned the node
deleted a node whose call returned None

Call rewire on the node 1. The call waits for its two children before it checks the node.

forest (roots)

empty

1 / 15

Gotchas1 of 4

The trap
Gotcha 1: Calling rewire(node.left) and rewire(node.right) without storing the results
Mistake
```
rewire(node.left)
rewire(node.right)
```
Fix
```
node.left = rewire(node.left)
node.right = rewire(node.right)
```
What happens: rewire(node.left) returns None when the left child is deleted, but the call does not change node.left. If the result is not stored, node still points at the deleted child. In [1,2,4,null,3] with to_delete = [3], node 2 still points at node 3, so the tree keeps the value 3 that should be gone.
Example: root = [1,2,4,null,3], to_delete = [3] (each tree is shown as its level-order list)
Mistake: returns [[1, 2, 4, None, 3]]Fix: returns [[1, 2, 4]]
Gotcha 2: Not adding the root when rewire(root) returns a node
Mistake
```
rewire(root)
```
Fix
```
root = rewire(root)
if root:
    forest.append(root)
```
What happens: Only a deleted node adds its children to forest. A root that stays has no deleted parent, so no other line adds it. Without the last three lines, a root that stays is missing from the answer. In [1,2,3] with to_delete = [3], node 3 is deleted and the tree [1,2] stays, but forest is empty.
Example: root = [1,2,3], to_delete = [3]
Mistake: returns []Fix: returns [[1, 2]]
Gotcha 3: Adding a child of a deleted node without checking that it exists
Mistake
```
forest.append(node.left)
forest.append(node.right)
```
Fix
```
if node.left:
    forest.append(node.left)
if node.right:
    forest.append(node.right)
```
What happens: A deleted node can have only one child, and None is not a tree. forest.append(node.right) adds None to the answer when node has no right child. In [1,2] with to_delete = [1], node 1 has no right child, so forest holds node 2 and None. The answer must hold only real roots.
Example: root = [1,2], to_delete = [1] (an empty list in the output stands for None)
Mistake: returns [[], [2]]Fix: returns [[2]]
Gotcha 4: Testing node.val in to_delete with the list instead of a set
What happens: in on a list reads the list from its start for every node. With N nodes and M values in to_delete, that costs O(N * M) instead of O(N + M). doomed = set(to_delete) makes each test O(1).

Not this one if…

The tree is a binary search tree and the rule is a range of values, as in Trim a Binary Search Tree (LC 669): the order tells you which whole side to drop without visiting it. Switch to BST Bounds. See BST Bounds
You build one tree from two input trees, as in Merge Two Binary Trees (LC 617): each call needs a pair of nodes, not one node. Switch to Two Tree Walk. See Two Tree Walk

Deep Dive

Why the parent must store what the call returns

Without the assignment, the node 2 would still point at the node 5 and the node 1 would still point at the node 3. The tree would keep the values that should be gone.

Why both children are rewired before the node is checked

Delete Leaves With a Given Value: the rule reads the rewired children

The cost, and the root

60-Second Pitch

Common Questions

How is Rewire Tree different from Bottom-Up DFS?: Bottom-Up DFS returns a number or a flag that describes a subtree. Rewire Tree returns the node itself, and the parent stores it as its child, so the call changes the shape of the tree.
Why does the root need special handling?: Every other node has a parent that stores the return value. The root has none, so delNodes stores the result in root and adds it to forest if it is not None.
What happens if a deleted node has a deleted child?: The child was rewired first and returned None, so the deleted node sees None in that place and does not add it to forest.
Why use a set for to_delete?: A set lookup is O(1). A list lookup reads up to M values for every node and makes the walk O(N * M).

SWE Reasoning

Spot it

The statement deletes, removes or cuts nodes of a tree by a rule.
The answer is the changed tree, or the roots of the pieces that remain.
Whether a node is removed can depend on what is left below it after its own children were changed.
You can say in one sentence what rewire(node) returns: the node that stays in that place, or None.

The invariant, step by step

Define rewire(node) as the node that stays in node's place after every deletion in its subtree, or None.
Rewire both children and store the results. After that, no pointer below node leads to a deleted node.
If the rule keeps node, return it. If the rule removes it, each child that stays lost its parent and goes to forest, and the call returns None.
The root has no parent, so delNodes stores the result in root and adds it to forest when it exists.

Traps

Not storing the result. rewire(node.left) alone leaves a deleted child attached to its parent.
Forgetting the root. A root that stays has no deleted parent to add it to forest.
Adding a missing child. A deleted node can have one child. Test if node.left: before forest.append(node.left).
A list for the deleted values. A set makes each test O(1).

Practice

Canonical LeetCode:Delete Nodes And Return Forest (LC 1110)Binary Tree Pruning (LC 814)Delete Leaves With a Given Value (LC 1325)Delete Node in a BST (LC 450)Invert Binary Tree (LC 226)

Theory Context•Depth-First Search (DFS)

Builds on Bottom-Up DFS, which you haven’t finished yet.

P3MediumBuilt on Bottom-Up DFS~3 min speedrun

Rewire Tree (Return the Node That Stays)

Built on

Bottom-Up DFSEach call returns the node that stays in its place, which may be None, and the parent stores that return value as its child.

The problem

Delete Nodes And Return Forest (LC 1110)(opens leetcode.com)

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.

Example 1

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

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

Node 3 is deleted, so its children 6 and 7 become roots of their own trees. Node 5 is deleted too, and it has no children. The tree of node 1 keeps nodes 1, 2 and 4.

Rewire Tree

tree + delete rule ➔ each call returns the node that stays (or None) ➔ parent stores it as its child

Spot it when: A rule deletes some nodes of a tree, and the answer is the changed tree or the roots of the pieces that remain. The parent must stop pointing at a deleted child.

Rewire Tree

Python

1	from typing import List, Optional
2
3	class TreeNode:
4	def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None):
5	self.val = val
6	self.left = left
7	self.right = right
8
9	def delNodes(root: Optional[TreeNode], to_delete: List[int]) -> List[Optional[TreeNode]]:
10	"""Delete Nodes And Return Forest: delete every node whose value is in to_delete and
11	return the roots of the trees that remain.
12	N = number of nodes. M = len(to_delete). H = height.
13	Time: O(N + M) \| Space: O(H + M) recursion stack and the set of deleted values, output not counted
14	"""
15	doomed = set(to_delete) # A set makes each test "is this value deleted?" O(1)
16	forest: List[Optional[TreeNode]] = [] # The root of every tree that remains
17
18	def rewire(node: Optional[TreeNode]) -> Optional[TreeNode]:
19	"""Returns the node that stays in node's place after every deletion in its
20	subtree, or None if node itself is deleted."""
21	if not node:
22	return None # An empty place stays empty
23	# 1. Rewire Both Subtrees First:
24	# Postorder: each child returns the node that stays in its place, and node
25	# stores it, so a deleted child stops being node's child.
26	node.left = rewire(node.left)
27	node.right = rewire(node.right)
28
29	# 2. Keep The Node:
30	# A node that is not deleted stays where it is, with its children already
31	# rewired.
32	if node.val not in doomed:
33	return node
34
35	# 3. Delete The Node:
36	# A deleted node loses its parent link, so each child that stays is the root of
37	# a new tree. Both children were rewired in step 1, so neither is deleted.
38	if node.left:
39	forest.append(node.left)
40	if node.right:
41	forest.append(node.right)
42	return None
43
44	# 4. Keep The Root If It Stays:
45	# The root has no parent to store the return value, so this function keeps it when
46	# rewire(root) returns a node.
47	root = rewire(root)
48	if root:
49	forest.append(root)
50	return forest

Invariant: rewire(node) returns node when it stays and None when it is deleted, and every pointer below node already points only at nodes that stay.

See it run

Rewire Tree, step by step

call now 1returns -answer not yet

Each call returns the node that stays in its place, or None. The parent stores the return value as its child.

now the call that is running
waiting a call that waits for its children
stays a node whose call returned the node
deleted a node whose call returned None

Call rewire on the node 1. The call waits for its two children before it checks the node.

forest (roots)

empty

1 / 15

Gotchas1 of 4

The trap
Gotcha 1: Calling rewire(node.left) and rewire(node.right) without storing the results
Mistake
```
rewire(node.left)
rewire(node.right)
```
Fix
```
node.left = rewire(node.left)
node.right = rewire(node.right)
```
What happens: rewire(node.left) returns None when the left child is deleted, but the call does not change node.left. If the result is not stored, node still points at the deleted child. In [1,2,4,null,3] with to_delete = [3], node 2 still points at node 3, so the tree keeps the value 3 that should be gone.
Example: root = [1,2,4,null,3], to_delete = [3] (each tree is shown as its level-order list)
Mistake: returns [[1, 2, 4, None, 3]]Fix: returns [[1, 2, 4]]
Gotcha 2: Not adding the root when rewire(root) returns a node
Mistake
```
rewire(root)
```
Fix
```
root = rewire(root)
if root:
    forest.append(root)
```
What happens: Only a deleted node adds its children to forest. A root that stays has no deleted parent, so no other line adds it. Without the last three lines, a root that stays is missing from the answer. In [1,2,3] with to_delete = [3], node 3 is deleted and the tree [1,2] stays, but forest is empty.
Example: root = [1,2,3], to_delete = [3]
Mistake: returns []Fix: returns [[1, 2]]
Gotcha 3: Adding a child of a deleted node without checking that it exists
Mistake
```
forest.append(node.left)
forest.append(node.right)
```
Fix
```
if node.left:
    forest.append(node.left)
if node.right:
    forest.append(node.right)
```
What happens: A deleted node can have only one child, and None is not a tree. forest.append(node.right) adds None to the answer when node has no right child. In [1,2] with to_delete = [1], node 1 has no right child, so forest holds node 2 and None. The answer must hold only real roots.
Example: root = [1,2], to_delete = [1] (an empty list in the output stands for None)
Mistake: returns [[], [2]]Fix: returns [[2]]
Gotcha 4: Testing node.val in to_delete with the list instead of a set
What happens: in on a list reads the list from its start for every node. With N nodes and M values in to_delete, that costs O(N * M) instead of O(N + M). doomed = set(to_delete) makes each test O(1).

Not this one if…

The tree is a binary search tree and the rule is a range of values, as in Trim a Binary Search Tree (LC 669): the order tells you which whole side to drop without visiting it. Switch to BST Bounds. See BST Bounds
You build one tree from two input trees, as in Merge Two Binary Trees (LC 617): each call needs a pair of nodes, not one node. Switch to Two Tree Walk. See Two Tree Walk

Deep Dive

Why the parent must store what the call returns

Without the assignment, the node 2 would still point at the node 5 and the node 1 would still point at the node 3. The tree would keep the values that should be gone.

Why both children are rewired before the node is checked

Delete Leaves With a Given Value: the rule reads the rewired children

The cost, and the root

60-Second Pitch

Common Questions

How is Rewire Tree different from Bottom-Up DFS?: Bottom-Up DFS returns a number or a flag that describes a subtree. Rewire Tree returns the node itself, and the parent stores it as its child, so the call changes the shape of the tree.
Why does the root need special handling?: Every other node has a parent that stores the return value. The root has none, so delNodes stores the result in root and adds it to forest if it is not None.
What happens if a deleted node has a deleted child?: The child was rewired first and returned None, so the deleted node sees None in that place and does not add it to forest.
Why use a set for to_delete?: A set lookup is O(1). A list lookup reads up to M values for every node and makes the walk O(N * M).

SWE Reasoning

Spot it

The statement deletes, removes or cuts nodes of a tree by a rule.
The answer is the changed tree, or the roots of the pieces that remain.
Whether a node is removed can depend on what is left below it after its own children were changed.
You can say in one sentence what rewire(node) returns: the node that stays in that place, or None.

The invariant, step by step

Define rewire(node) as the node that stays in node's place after every deletion in its subtree, or None.
Rewire both children and store the results. After that, no pointer below node leads to a deleted node.
If the rule keeps node, return it. If the rule removes it, each child that stays lost its parent and goes to forest, and the call returns None.
The root has no parent, so delNodes stores the result in root and adds it to forest when it exists.

Traps

Not storing the result. rewire(node.left) alone leaves a deleted child attached to its parent.
Forgetting the root. A root that stays has no deleted parent to add it to forest.
Adding a missing child. A deleted node can have one child. Test if node.left: before forest.append(node.left).
A list for the deleted values. A set makes each test O(1).

Practice

Canonical LeetCode:Delete Nodes And Return Forest (LC 1110)Binary Tree Pruning (LC 814)Delete Leaves With a Given Value (LC 1325)Delete Node in a BST (LC 450)Invert Binary Tree (LC 226)

Theory Context•Depth-First Search (DFS)

Builds on Bottom-Up DFS, which you haven’t finished yet.

P3MediumBuilt on Bottom-Up DFS~3 min speedrun

Rewire Tree (Return the Node That Stays)

Built on

Bottom-Up DFSEach call returns the node that stays in its place, which may be None, and the parent stores that return value as its child.

The problem

Delete Nodes And Return Forest (LC 1110)(opens leetcode.com)

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.

Example 1

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

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

Node 3 is deleted, so its children 6 and 7 become roots of their own trees. Node 5 is deleted too, and it has no children. The tree of node 1 keeps nodes 1, 2 and 4.

Rewire Tree

tree + delete rule ➔ each call returns the node that stays (or None) ➔ parent stores it as its child

Spot it when: A rule deletes some nodes of a tree, and the answer is the changed tree or the roots of the pieces that remain. The parent must stop pointing at a deleted child.

Rewire Tree

Python

1	from typing import List, Optional
2
3	class TreeNode:
4	def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None):
5	self.val = val
6	self.left = left
7	self.right = right
8
9	def delNodes(root: Optional[TreeNode], to_delete: List[int]) -> List[Optional[TreeNode]]:
10	"""Delete Nodes And Return Forest: delete every node whose value is in to_delete and
11	return the roots of the trees that remain.
12	N = number of nodes. M = len(to_delete). H = height.
13	Time: O(N + M) \| Space: O(H + M) recursion stack and the set of deleted values, output not counted
14	"""
15	doomed = set(to_delete) # A set makes each test "is this value deleted?" O(1)
16	forest: List[Optional[TreeNode]] = [] # The root of every tree that remains
17
18	def rewire(node: Optional[TreeNode]) -> Optional[TreeNode]:
19	"""Returns the node that stays in node's place after every deletion in its
20	subtree, or None if node itself is deleted."""
21	if not node:
22	return None # An empty place stays empty
23	# 1. Rewire Both Subtrees First:
24	# Postorder: each child returns the node that stays in its place, and node
25	# stores it, so a deleted child stops being node's child.
26	node.left = rewire(node.left)
27	node.right = rewire(node.right)
28
29	# 2. Keep The Node:
30	# A node that is not deleted stays where it is, with its children already
31	# rewired.
32	if node.val not in doomed:
33	return node
34
35	# 3. Delete The Node:
36	# A deleted node loses its parent link, so each child that stays is the root of
37	# a new tree. Both children were rewired in step 1, so neither is deleted.
38	if node.left:
39	forest.append(node.left)
40	if node.right:
41	forest.append(node.right)
42	return None
43
44	# 4. Keep The Root If It Stays:
45	# The root has no parent to store the return value, so this function keeps it when
46	# rewire(root) returns a node.
47	root = rewire(root)
48	if root:
49	forest.append(root)
50	return forest

Invariant: rewire(node) returns node when it stays and None when it is deleted, and every pointer below node already points only at nodes that stay.

See it run

Rewire Tree, step by step

call now 1returns -answer not yet

Each call returns the node that stays in its place, or None. The parent stores the return value as its child.

now the call that is running
waiting a call that waits for its children
stays a node whose call returned the node
deleted a node whose call returned None

Call rewire on the node 1. The call waits for its two children before it checks the node.

forest (roots)

empty

1 / 15

Gotchas1 of 4

The trap
Gotcha 1: Calling rewire(node.left) and rewire(node.right) without storing the results
Mistake
```
rewire(node.left)
rewire(node.right)
```
Fix
```
node.left = rewire(node.left)
node.right = rewire(node.right)
```
What happens: rewire(node.left) returns None when the left child is deleted, but the call does not change node.left. If the result is not stored, node still points at the deleted child. In [1,2,4,null,3] with to_delete = [3], node 2 still points at node 3, so the tree keeps the value 3 that should be gone.
Example: root = [1,2,4,null,3], to_delete = [3] (each tree is shown as its level-order list)
Mistake: returns [[1, 2, 4, None, 3]]Fix: returns [[1, 2, 4]]
Gotcha 2: Not adding the root when rewire(root) returns a node
Mistake
```
rewire(root)
```
Fix
```
root = rewire(root)
if root:
    forest.append(root)
```
What happens: Only a deleted node adds its children to forest. A root that stays has no deleted parent, so no other line adds it. Without the last three lines, a root that stays is missing from the answer. In [1,2,3] with to_delete = [3], node 3 is deleted and the tree [1,2] stays, but forest is empty.
Example: root = [1,2,3], to_delete = [3]
Mistake: returns []Fix: returns [[1, 2]]
Gotcha 3: Adding a child of a deleted node without checking that it exists
Mistake
```
forest.append(node.left)
forest.append(node.right)
```
Fix
```
if node.left:
    forest.append(node.left)
if node.right:
    forest.append(node.right)
```
What happens: A deleted node can have only one child, and None is not a tree. forest.append(node.right) adds None to the answer when node has no right child. In [1,2] with to_delete = [1], node 1 has no right child, so forest holds node 2 and None. The answer must hold only real roots.
Example: root = [1,2], to_delete = [1] (an empty list in the output stands for None)
Mistake: returns [[], [2]]Fix: returns [[2]]
Gotcha 4: Testing node.val in to_delete with the list instead of a set
What happens: in on a list reads the list from its start for every node. With N nodes and M values in to_delete, that costs O(N * M) instead of O(N + M). doomed = set(to_delete) makes each test O(1).

Not this one if…

The tree is a binary search tree and the rule is a range of values, as in Trim a Binary Search Tree (LC 669): the order tells you which whole side to drop without visiting it. Switch to BST Bounds. See BST Bounds
You build one tree from two input trees, as in Merge Two Binary Trees (LC 617): each call needs a pair of nodes, not one node. Switch to Two Tree Walk. See Two Tree Walk

Deep Dive

Why the parent must store what the call returns

Without the assignment, the node 2 would still point at the node 5 and the node 1 would still point at the node 3. The tree would keep the values that should be gone.

Why both children are rewired before the node is checked

Delete Leaves With a Given Value: the rule reads the rewired children

The cost, and the root

60-Second Pitch

Common Questions

How is Rewire Tree different from Bottom-Up DFS?: Bottom-Up DFS returns a number or a flag that describes a subtree. Rewire Tree returns the node itself, and the parent stores it as its child, so the call changes the shape of the tree.
Why does the root need special handling?: Every other node has a parent that stores the return value. The root has none, so delNodes stores the result in root and adds it to forest if it is not None.
What happens if a deleted node has a deleted child?: The child was rewired first and returned None, so the deleted node sees None in that place and does not add it to forest.
Why use a set for to_delete?: A set lookup is O(1). A list lookup reads up to M values for every node and makes the walk O(N * M).

SWE Reasoning

Spot it

The statement deletes, removes or cuts nodes of a tree by a rule.
The answer is the changed tree, or the roots of the pieces that remain.
Whether a node is removed can depend on what is left below it after its own children were changed.
You can say in one sentence what rewire(node) returns: the node that stays in that place, or None.

The invariant, step by step

Define rewire(node) as the node that stays in node's place after every deletion in its subtree, or None.
Rewire both children and store the results. After that, no pointer below node leads to a deleted node.
If the rule keeps node, return it. If the rule removes it, each child that stays lost its parent and goes to forest, and the call returns None.
The root has no parent, so delNodes stores the result in root and adds it to forest when it exists.

Traps

Not storing the result. rewire(node.left) alone leaves a deleted child attached to its parent.
Forgetting the root. A root that stays has no deleted parent to add it to forest.
Adding a missing child. A deleted node can have one child. Test if node.left: before forest.append(node.left).
A list for the deleted values. A set makes each test O(1).

Practice

Canonical LeetCode:Delete Nodes And Return Forest (LC 1110)Binary Tree Pruning (LC 814)Delete Leaves With a Given Value (LC 1325)Delete Node in a BST (LC 450)Invert Binary Tree (LC 226)