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.

P2HardBuilt on Bottom-Up DFS~5 min speedrun

Rerooting a Tree (Answer for Every Root)

Built on

Bottom-Up DFSA second pass walks down and hands each child the answer for everything outside its subtree, so every node gets the answer as if it were the root.

The problem

Sum of Distances in Tree (LC 834)(opens leetcode.com)

A tree has n nodes numbered 0 to n - 1, joined by n - 1 undirected edges. The edges list holds the edges: [a, b] means that node a and node b are joined. The distance between two nodes is the number of edges on the one path that joins them.

For every node i, add up the distances from node i to all other nodes. Return these n sums as a list answer, where answer[i] is the sum for node i.

The sums are independent: each node is a separate question, as if that node were the root of the tree.

Example 1

Input:n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]

Output:[8,12,6,10,10,10]

Node 0 is 1 step from node 1, 1 step from node 2, and 2 steps from each of nodes 3, 4 and 5, so answer[0] = 1 + 1 + 2 + 2 + 2 = 8. Node 1 is 1 step from node 0 and 2 steps from node 2, then 3 steps from each of nodes 3, 4 and 5, so answer[1] = 12. The other sums follow the same way.

Reroot

tree ➔ first pass: subtree answers ➔ second pass: outside answers ➔ answer for every root

Spot it when: The problem asks for an answer for every node, as if that node were the root: the total distance to all other nodes, the cost to reach every other node, or the time to reach the farthest node.

Reroot

Python

1	from typing import Callable, TypeVar
2
3	V = TypeVar("V")
4
5
6	def reroot(n: int, edges: list[list[int]], empty: V, lift: Callable[[V, int, int], V],
7	merge: Callable[[V, V], V], finish: Callable[[int, V], V]) -> list[V]:
8	"""Rerooting: the answer for every node, as if that node were the root of the tree.
9	lift(value, source, target) moves the value of the piece that hangs at source across
10	the edge to target.
11	merge(a, b) combines two pieces, and empty is its identity. finish(node, pieces)
12	builds the answer for node.
13	Precondition: the answer for a node depends only on the pieces that hang from it,
14	and merge is associative.
15	N = number of nodes. T = the cost of one lift, merge or finish call.
16	Time: O(N * T) \| Space: O(N)
17	"""
18	# neighbors[v] lists the nodes joined to v by an edge
19	neighbors: list[list[int]] = [[] for _ in range(n)]
20	for a, b in edges:
21	neighbors[a].append(b)
22	neighbors[b].append(a)
23
24	# 1. Order The Nodes:
25	# Root the tree at node 0. Every parent comes before its children in order, so one
26	# loop in each direction is enough.
27	parent = [-1] * n
28	order = [0]
29	for node in order:
30	for nxt in neighbors[node]:
31	if nxt != parent[node]:
32	parent[nxt] = node
33	order.append(nxt)
34
35	# 2. First Pass, Children Before Parents:
36	# down[node] is the answer for the subtree of node, built only from the answers of
37	# its children.
38	down = [empty] * n
39	for node in reversed(order):
40	pieces = empty
41	for child in neighbors[node]:
42	if child != parent[node]:
43	pieces = merge(pieces, lift(down[child], child, node))
44	down[node] = finish(node, pieces)
45
46	# 3. Second Pass, Parents Before Children:
47	# outside[child] is the answer for everything outside the subtree of child, as a
48	# tree that hangs from its parent.
49	# It merges the pieces of the parent's other children and the piece above the
50	# parent, so each child skips its own piece.
51	outside = [empty] * n
52	answer = [empty] * n
53	for node in order:
54	children = [c for c in neighbors[node] if c != parent[node]]
55	lifted = [lift(down[c], c, node) for c in children]
56	before = [empty if parent[node] < 0 else lift(outside[node], parent[node], node)]
57	for piece in lifted:
58	before.append(merge(before[-1], piece))
59	answer[node] = finish(node, before[-1])
60	after = empty
61	for i in range(len(children) - 1, -1, -1):
62	outside[children[i]] = finish(node, merge(before[i], after))
63	after = merge(lifted[i], after)
64	return answer

Invariant: When the second pass reaches node, answer[node] is the answer for the whole tree rooted at node: down[node] covers its own subtree, and the part handed down from its parent covers everything outside it.

Moving the root across one edge changes the answer in a way you can compute, so solve the tree once with node 0 as the root, and then hand every child the answer for everything outside its subtree. The first pass runs from the leaves up and fills count[node] and down[node] for the subtree of each node. The second pass runs from the root down. For each node, outside_count and outside_sum come from the finished answer of its parent, so answer[node] = down[node] + outside_sum + outside_count is the answer as if node were the root. Every node is handled twice, so no node starts a new walk of the whole tree. The trap is outside_count: each node outside the subtree is one step farther from node than from its parent, so a sum without outside_count is too small.

See it run

Sum of Distances in Tree with rerooting, step by step

Each circle is a node. The three rows under the tree show count, down and answer for every node.

node the node being handled
done a node that is already handled
total the parent, or the edge, that receives or hands down a total

The tree has 6 nodes. Node 0 is the root, and the lists count, down and answer start empty.

count

0: 1

1: 1

2: 1

3: 1

4: 1

5: 1

down

0: 0

1: 0

2: 0

3: 0

4: 0

5: 0

answer

0: ?

1: ?

2: ?

3: ?

4: ?

5: ?

1 / 14

Gotchas1 of 5

The trap
Gotcha 1: Leaving out outside_count when the root moves to node
Mistake
```
answer[node] = down[node] + outside_sum
```
Fix
```
answer[node] = down[node] + outside_sum + outside_count
```
What happens: outside_sum holds the distances from the parent to the nodes outside the subtree of node. Each of those nodes is one step farther from node than from its parent. outside_count adds that one step for every outside node. Without it, every answer except the root's is too small. In the six-node example, node 1 gets 7 instead of 12.
Example: Sum of Distances in Tree (LC 834): n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Mistake: returns [8, 7, 4, 3, 3, 3]Fix: returns [8, 12, 6, 10, 10, 10]
Gotcha 2: Taking only down[node] out of the parent's total
Mistake
```
outside_sum = answer[parent[node]] - down[node]
```
Fix
```
outside_sum = answer[parent[node]] - down[node] - count[node]
```
What happens: answer[parent[node]] counts every node of the subtree of node at its distance from the parent. That distance is one more than its distance from node. Taking out down[node] removes the distances from node, and count[node] extra steps stay in outside_sum. Take out count[node] as well. In the six-node example, node 1 gets 13 instead of 12.
Example: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Mistake: returns [8, 13, 10, 15, 15, 15]Fix: returns [8, 12, 6, 10, 10, 10]
Gotcha 3: Running the second pass over reversed(order[1:])
Mistake
```
for node in reversed(order[1:]):
```
Fix
```
for node in order[1:]:
```
What happens: Each node needs the finished answer of its parent. order lists every parent before its children, so only the forward order has that answer ready. In the reversed order, answer[parent[node]] is still 0 when a leaf is handled. In the six-node example, nodes 3, 4 and 5 get 4 instead of 10.
Example: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Mistake: returns [8, 12, 6, 4, 4, 4]Fix: returns [8, 12, 6, 10, 10, 10]
Gotcha 4: Adding down[node] without count[node] in the first pass
Mistake
```
down[parent[node]] += down[node]
```
Fix
```
down[parent[node]] += down[node] + count[node]
```
What happens: down[node] holds distances measured from node. Seen from the parent, every node of that subtree is one step farther, and there are count[node] of them. Without count[node], every down value is too small. With n = 3 and edges = [[0,1],[0,2]], the answer for node 0 is 2, and this mistake gives 0.
Example: n = 3, edges = [[0,1],[0,2]]
Mistake: returns [0, 1, 1]Fix: returns [2, 3, 3]
Gotcha 5: Walking both passes with recursion on a long path
What happens: A path of 3 * 10^4 nodes is a valid input of Sum of Distances in Tree (LC 834). A recursive walk goes one call deeper for every node, so it goes 3 * 10^4 calls deep. Python stops at about 1000 nested calls by default and raises a RecursionError. The blueprint builds order with a loop and visits it forward and in reverse, so it has no depth limit.

Not this one if…

You need one answer for one fixed root, as in Maximum Depth of Binary Tree (LC 104): the first pass from the leaves up is enough. A question about one given node, such as All Nodes Distance K in Binary Tree (LC 863), needs each node's parent and one search from that node, not a second pass for every node. See Bottom-Up DFS
The input is an undirected tree and you need one number for the whole tree, as in Tree Diameter (LC 1245): the best value found at any node while walking up is the answer. Reroot only when the answer is a list with one entry per node. See Tree Diameter DP
Each node chooses a state that limits its children, as in House Robber III (LC 337), and the answer is for one fixed root. Several states per node answer a choice at a node. Rerooting answers a different question: which node is the root. See Tree State DP

Deep Dive

Why two neighbouring roots give almost the same answer

Some problems ask for one answer for every node, as if that node were the root. The slow way starts a new walk of the whole tree from every node. That costs N walks over N nodes each.

Look at two nodes joined by one edge. If the root moves from the first node to the second, the nodes on the second node's side each get one step closer. The nodes on the other side each get one step farther. No other distance changes.

So the answer for a child follows from the answer for its parent, plus a correction that only needs two numbers: how many nodes are on each side, and how far they were. This card computes those numbers once, with node 0 as the root.

The first pass up and the second pass down

The first pass is the walk of Bottom-Up DFS. For each node, count[node] is the number of nodes in its subtree, and down[node] is the sum of their distances from node. A parent adds down[node] + count[node] for each child, because each node of the child's subtree is one step farther from the parent.

The second pass goes from the root down. The root has nothing outside its subtree, so answer[0] = down[0]. For a child, answer[parent[node]] is already final. The outside_count = n - count[node] nodes outside the subtree of node are outside_sum = answer[parent[node]] - down[node] - count[node] away from the parent in total.

Each of those outside nodes is one step farther from node than from its parent. So answer[node] = down[node] + outside_sum + outside_count. In the six-node example the board shows this for node 1: 0 + 7 + 5 = 12.

The trap: the outside part is part of the answer

The line answer[node] = down[node] + outside_sum + outside_count has three parts. A common mistake is to leave out outside_count. The outside distances are then measured from the parent, not from node.

In the six-node example, node 1 gets 7 instead of 12, and the whole answer becomes [8, 7, 4, 3, 3, 3]. Every answer except the root's is too small.

The second pass must also run parents first. order lists every parent before its children, so for node in order[1:] works. In reverse order, a leaf reads answer[parent[node]] while it is still 0.

The cost, and when this card does not apply

Building order and the two passes each handle every node once. The time is O(N) and the space is O(N). The code uses no recursion, so a path of 30,000 nodes is safe.

When the combine step is not a sum, the same two passes work with a different correction. Minimum Edge Reversals So Every Node Is Reachable (LC 2858) changes the answer by exactly one across each edge. Time Taken to Mark All Nodes (LC 3241) keeps the two longest paths below each node.

If you need one answer for one fixed root, the first pass is enough: use Bottom-Up DFS. If you need the answer for one given node only, as in All Nodes Distance K in Binary Tree (LC 863), a parent for each node and one search from that node is enough.

60-Second Pitch

"The problem needs the answer for every node as if it were the root, so I use rerooting. I root the tree at node 0 and run a first pass from the leaves up. It gives each node its subtree size and the sum of distances below it. Then I run a second pass from the root down. Each child takes its parent's answer, removes its own subtree, and adds one step for every node outside it. It is correct because the parent's answer is final before the child is handled, and moving the root across one edge changes every distance by exactly one step. Each node is handled twice, so the time is O(N) and the space is O(N)."

Common Questions

Why not run a search from every node?: That costs O(N) per node, so O(N^2) in total. With 30,000 nodes that is about 900 million steps. Rerooting reuses the answer of the parent, so each node costs O(1) after the first pass.
What does outside_count do?: It counts the nodes outside the subtree of node. Each of them is one step farther from node than from its parent, so outside_count extra steps are added to outside_sum. Without it, the answers are too small.
What if the combine step is a maximum and not a sum?: A maximum cannot be undone by subtraction. Keep the largest and the second largest value from the children of each node, and hand each child the best value that does not come through itself. Time Taken to Mark All Nodes (LC 3241) works this way.
How is this different from Tree Diameter (LC 1245)?: Tree Diameter needs one number for the whole tree, found while walking up. Rerooting needs a list with one entry per node, so it adds a second pass down.
Would a parent map and a search from one node also work?: Yes, for a question about one given node, such as All Nodes Distance K in Binary Tree (LC 863). A parent map lets the search move up as well as down. For an answer at every node, that search would repeat for every node, which costs O(N^2).

SWE Reasoning

Spot it

The problem returns a list with one answer per node, each as if that node were the root.
A walk from every node would cost O(N^2), and N is large.
The answers of two neighbouring nodes differ by a correction you can compute.
The tree is given as an edge list, so there is no fixed root.

The invariant, step by step

Root the tree at node 0 and order the nodes so that every parent comes before its children.
First pass, children before parents: count[node] and down[node] describe only the subtree of node.
The root has nothing outside its subtree, so answer[0] = down[0] is final.
Second pass, parents before children: answer[parent[node]] is final, so outside_count and outside_sum are known.
answer[node] = down[node] + outside_sum + outside_count is the answer as if node were the root, and every node is handled twice.

Traps

Leaving out outside_count. Each outside node is one step farther from node than from its parent.
Taking out only down[node]. The parent's total also holds count[node] extra steps for the subtree.
A second pass in reverse order. A child then reads a parent answer that is still 0.
Recursion on a long path. A path of 30,000 nodes passes Python's default limit, so build order with a loop.

Practice

Canonical LeetCode:Sum of Distances in Tree (LC 834)Count Number of Possible Root Nodes (LC 2581)Minimum Edge Reversals So Every Node Is Reachable (LC 2858)Time Taken to Mark All Nodes (LC 3241)

Theory Context•Depth-First Search (DFS)

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

P2HardBuilt on Bottom-Up DFS~5 min speedrun

Rerooting a Tree (Answer for Every Root)

Built on

Bottom-Up DFSA second pass walks down and hands each child the answer for everything outside its subtree, so every node gets the answer as if it were the root.

The problem

Sum of Distances in Tree (LC 834)(opens leetcode.com)

For every node i, add up the distances from node i to all other nodes. Return these n sums as a list answer, where answer[i] is the sum for node i.

The sums are independent: each node is a separate question, as if that node were the root of the tree.

Example 1

Input:n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]

Output:[8,12,6,10,10,10]

Reroot

tree ➔ first pass: subtree answers ➔ second pass: outside answers ➔ answer for every root

Reroot

Python

1	from typing import Callable, TypeVar
2
3	V = TypeVar("V")
4
5
6	def reroot(n: int, edges: list[list[int]], empty: V, lift: Callable[[V, int, int], V],
7	merge: Callable[[V, V], V], finish: Callable[[int, V], V]) -> list[V]:
8	"""Rerooting: the answer for every node, as if that node were the root of the tree.
9	lift(value, source, target) moves the value of the piece that hangs at source across
10	the edge to target.
11	merge(a, b) combines two pieces, and empty is its identity. finish(node, pieces)
12	builds the answer for node.
13	Precondition: the answer for a node depends only on the pieces that hang from it,
14	and merge is associative.
15	N = number of nodes. T = the cost of one lift, merge or finish call.
16	Time: O(N * T) \| Space: O(N)
17	"""
18	# neighbors[v] lists the nodes joined to v by an edge
19	neighbors: list[list[int]] = [[] for _ in range(n)]
20	for a, b in edges:
21	neighbors[a].append(b)
22	neighbors[b].append(a)
23
24	# 1. Order The Nodes:
25	# Root the tree at node 0. Every parent comes before its children in order, so one
26	# loop in each direction is enough.
27	parent = [-1] * n
28	order = [0]
29	for node in order:
30	for nxt in neighbors[node]:
31	if nxt != parent[node]:
32	parent[nxt] = node
33	order.append(nxt)
34
35	# 2. First Pass, Children Before Parents:
36	# down[node] is the answer for the subtree of node, built only from the answers of
37	# its children.
38	down = [empty] * n
39	for node in reversed(order):
40	pieces = empty
41	for child in neighbors[node]:
42	if child != parent[node]:
43	pieces = merge(pieces, lift(down[child], child, node))
44	down[node] = finish(node, pieces)
45
46	# 3. Second Pass, Parents Before Children:
47	# outside[child] is the answer for everything outside the subtree of child, as a
48	# tree that hangs from its parent.
49	# It merges the pieces of the parent's other children and the piece above the
50	# parent, so each child skips its own piece.
51	outside = [empty] * n
52	answer = [empty] * n
53	for node in order:
54	children = [c for c in neighbors[node] if c != parent[node]]
55	lifted = [lift(down[c], c, node) for c in children]
56	before = [empty if parent[node] < 0 else lift(outside[node], parent[node], node)]
57	for piece in lifted:
58	before.append(merge(before[-1], piece))
59	answer[node] = finish(node, before[-1])
60	after = empty
61	for i in range(len(children) - 1, -1, -1):
62	outside[children[i]] = finish(node, merge(before[i], after))
63	after = merge(lifted[i], after)
64	return answer

See it run

Sum of Distances in Tree with rerooting, step by step

Each circle is a node. The three rows under the tree show count, down and answer for every node.

node the node being handled
done a node that is already handled
total the parent, or the edge, that receives or hands down a total

The tree has 6 nodes. Node 0 is the root, and the lists count, down and answer start empty.

count

0: 1

1: 1

2: 1

3: 1

4: 1

5: 1

down

0: 0

1: 0

2: 0

3: 0

4: 0

5: 0

answer

0: ?

1: ?

2: ?

3: ?

4: ?

5: ?

1 / 14

Gotchas1 of 5

The trap
Gotcha 1: Leaving out outside_count when the root moves to node
Mistake
```
answer[node] = down[node] + outside_sum
```
Fix
```
answer[node] = down[node] + outside_sum + outside_count
```
What happens: outside_sum holds the distances from the parent to the nodes outside the subtree of node. Each of those nodes is one step farther from node than from its parent. outside_count adds that one step for every outside node. Without it, every answer except the root's is too small. In the six-node example, node 1 gets 7 instead of 12.
Example: Sum of Distances in Tree (LC 834): n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Mistake: returns [8, 7, 4, 3, 3, 3]Fix: returns [8, 12, 6, 10, 10, 10]
Gotcha 2: Taking only down[node] out of the parent's total
Mistake
```
outside_sum = answer[parent[node]] - down[node]
```
Fix
```
outside_sum = answer[parent[node]] - down[node] - count[node]
```
What happens: answer[parent[node]] counts every node of the subtree of node at its distance from the parent. That distance is one more than its distance from node. Taking out down[node] removes the distances from node, and count[node] extra steps stay in outside_sum. Take out count[node] as well. In the six-node example, node 1 gets 13 instead of 12.
Example: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Mistake: returns [8, 13, 10, 15, 15, 15]Fix: returns [8, 12, 6, 10, 10, 10]
Gotcha 3: Running the second pass over reversed(order[1:])
Mistake
```
for node in reversed(order[1:]):
```
Fix
```
for node in order[1:]:
```
What happens: Each node needs the finished answer of its parent. order lists every parent before its children, so only the forward order has that answer ready. In the reversed order, answer[parent[node]] is still 0 when a leaf is handled. In the six-node example, nodes 3, 4 and 5 get 4 instead of 10.
Example: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Mistake: returns [8, 12, 6, 4, 4, 4]Fix: returns [8, 12, 6, 10, 10, 10]
Gotcha 4: Adding down[node] without count[node] in the first pass
Mistake
```
down[parent[node]] += down[node]
```
Fix
```
down[parent[node]] += down[node] + count[node]
```
What happens: down[node] holds distances measured from node. Seen from the parent, every node of that subtree is one step farther, and there are count[node] of them. Without count[node], every down value is too small. With n = 3 and edges = [[0,1],[0,2]], the answer for node 0 is 2, and this mistake gives 0.
Example: n = 3, edges = [[0,1],[0,2]]
Mistake: returns [0, 1, 1]Fix: returns [2, 3, 3]
Gotcha 5: Walking both passes with recursion on a long path
What happens: A path of 3 * 10^4 nodes is a valid input of Sum of Distances in Tree (LC 834). A recursive walk goes one call deeper for every node, so it goes 3 * 10^4 calls deep. Python stops at about 1000 nested calls by default and raises a RecursionError. The blueprint builds order with a loop and visits it forward and in reverse, so it has no depth limit.

Not this one if…

You need one answer for one fixed root, as in Maximum Depth of Binary Tree (LC 104): the first pass from the leaves up is enough. A question about one given node, such as All Nodes Distance K in Binary Tree (LC 863), needs each node's parent and one search from that node, not a second pass for every node. See Bottom-Up DFS
The input is an undirected tree and you need one number for the whole tree, as in Tree Diameter (LC 1245): the best value found at any node while walking up is the answer. Reroot only when the answer is a list with one entry per node. See Tree Diameter DP
Each node chooses a state that limits its children, as in House Robber III (LC 337), and the answer is for one fixed root. Several states per node answer a choice at a node. Rerooting answers a different question: which node is the root. See Tree State DP

Deep Dive

Why two neighbouring roots give almost the same answer

Some problems ask for one answer for every node, as if that node were the root. The slow way starts a new walk of the whole tree from every node. That costs N walks over N nodes each.

The first pass up and the second pass down

The trap: the outside part is part of the answer

In the six-node example, node 1 gets 7 instead of 12, and the whole answer becomes [8, 7, 4, 3, 3, 3]. Every answer except the root's is too small.

The cost, and when this card does not apply

Building order and the two passes each handle every node once. The time is O(N) and the space is O(N). The code uses no recursion, so a path of 30,000 nodes is safe.

60-Second Pitch

Common Questions

Why not run a search from every node?: That costs O(N) per node, so O(N^2) in total. With 30,000 nodes that is about 900 million steps. Rerooting reuses the answer of the parent, so each node costs O(1) after the first pass.
What does outside_count do?: It counts the nodes outside the subtree of node. Each of them is one step farther from node than from its parent, so outside_count extra steps are added to outside_sum. Without it, the answers are too small.
What if the combine step is a maximum and not a sum?: A maximum cannot be undone by subtraction. Keep the largest and the second largest value from the children of each node, and hand each child the best value that does not come through itself. Time Taken to Mark All Nodes (LC 3241) works this way.
How is this different from Tree Diameter (LC 1245)?: Tree Diameter needs one number for the whole tree, found while walking up. Rerooting needs a list with one entry per node, so it adds a second pass down.
Would a parent map and a search from one node also work?: Yes, for a question about one given node, such as All Nodes Distance K in Binary Tree (LC 863). A parent map lets the search move up as well as down. For an answer at every node, that search would repeat for every node, which costs O(N^2).

SWE Reasoning

Spot it

The problem returns a list with one answer per node, each as if that node were the root.
A walk from every node would cost O(N^2), and N is large.
The answers of two neighbouring nodes differ by a correction you can compute.
The tree is given as an edge list, so there is no fixed root.

The invariant, step by step

Root the tree at node 0 and order the nodes so that every parent comes before its children.
First pass, children before parents: count[node] and down[node] describe only the subtree of node.
The root has nothing outside its subtree, so answer[0] = down[0] is final.
Second pass, parents before children: answer[parent[node]] is final, so outside_count and outside_sum are known.
answer[node] = down[node] + outside_sum + outside_count is the answer as if node were the root, and every node is handled twice.

Traps

Leaving out outside_count. Each outside node is one step farther from node than from its parent.
Taking out only down[node]. The parent's total also holds count[node] extra steps for the subtree.
A second pass in reverse order. A child then reads a parent answer that is still 0.
Recursion on a long path. A path of 30,000 nodes passes Python's default limit, so build order with a loop.

Practice

Canonical LeetCode:Sum of Distances in Tree (LC 834)Count Number of Possible Root Nodes (LC 2581)Minimum Edge Reversals So Every Node Is Reachable (LC 2858)Time Taken to Mark All Nodes (LC 3241)

Theory Context•Depth-First Search (DFS)

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

P2HardBuilt on Bottom-Up DFS~5 min speedrun

Rerooting a Tree (Answer for Every Root)

Built on

Bottom-Up DFSA second pass walks down and hands each child the answer for everything outside its subtree, so every node gets the answer as if it were the root.

The problem

Sum of Distances in Tree (LC 834)(opens leetcode.com)

For every node i, add up the distances from node i to all other nodes. Return these n sums as a list answer, where answer[i] is the sum for node i.

The sums are independent: each node is a separate question, as if that node were the root of the tree.

Example 1

Input:n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]

Output:[8,12,6,10,10,10]

Reroot

tree ➔ first pass: subtree answers ➔ second pass: outside answers ➔ answer for every root

Reroot

Python

1	from typing import Callable, TypeVar
2
3	V = TypeVar("V")
4
5
6	def reroot(n: int, edges: list[list[int]], empty: V, lift: Callable[[V, int, int], V],
7	merge: Callable[[V, V], V], finish: Callable[[int, V], V]) -> list[V]:
8	"""Rerooting: the answer for every node, as if that node were the root of the tree.
9	lift(value, source, target) moves the value of the piece that hangs at source across
10	the edge to target.
11	merge(a, b) combines two pieces, and empty is its identity. finish(node, pieces)
12	builds the answer for node.
13	Precondition: the answer for a node depends only on the pieces that hang from it,
14	and merge is associative.
15	N = number of nodes. T = the cost of one lift, merge or finish call.
16	Time: O(N * T) \| Space: O(N)
17	"""
18	# neighbors[v] lists the nodes joined to v by an edge
19	neighbors: list[list[int]] = [[] for _ in range(n)]
20	for a, b in edges:
21	neighbors[a].append(b)
22	neighbors[b].append(a)
23
24	# 1. Order The Nodes:
25	# Root the tree at node 0. Every parent comes before its children in order, so one
26	# loop in each direction is enough.
27	parent = [-1] * n
28	order = [0]
29	for node in order:
30	for nxt in neighbors[node]:
31	if nxt != parent[node]:
32	parent[nxt] = node
33	order.append(nxt)
34
35	# 2. First Pass, Children Before Parents:
36	# down[node] is the answer for the subtree of node, built only from the answers of
37	# its children.
38	down = [empty] * n
39	for node in reversed(order):
40	pieces = empty
41	for child in neighbors[node]:
42	if child != parent[node]:
43	pieces = merge(pieces, lift(down[child], child, node))
44	down[node] = finish(node, pieces)
45
46	# 3. Second Pass, Parents Before Children:
47	# outside[child] is the answer for everything outside the subtree of child, as a
48	# tree that hangs from its parent.
49	# It merges the pieces of the parent's other children and the piece above the
50	# parent, so each child skips its own piece.
51	outside = [empty] * n
52	answer = [empty] * n
53	for node in order:
54	children = [c for c in neighbors[node] if c != parent[node]]
55	lifted = [lift(down[c], c, node) for c in children]
56	before = [empty if parent[node] < 0 else lift(outside[node], parent[node], node)]
57	for piece in lifted:
58	before.append(merge(before[-1], piece))
59	answer[node] = finish(node, before[-1])
60	after = empty
61	for i in range(len(children) - 1, -1, -1):
62	outside[children[i]] = finish(node, merge(before[i], after))
63	after = merge(lifted[i], after)
64	return answer

See it run

Sum of Distances in Tree with rerooting, step by step

Each circle is a node. The three rows under the tree show count, down and answer for every node.

node the node being handled
done a node that is already handled
total the parent, or the edge, that receives or hands down a total

The tree has 6 nodes. Node 0 is the root, and the lists count, down and answer start empty.

count

0: 1

1: 1

2: 1

3: 1

4: 1

5: 1

down

0: 0

1: 0

2: 0

3: 0

4: 0

5: 0

answer

0: ?

1: ?

2: ?

3: ?

4: ?

5: ?

1 / 14

Gotchas1 of 5

The trap
Gotcha 1: Leaving out outside_count when the root moves to node
Mistake
```
answer[node] = down[node] + outside_sum
```
Fix
```
answer[node] = down[node] + outside_sum + outside_count
```
What happens: outside_sum holds the distances from the parent to the nodes outside the subtree of node. Each of those nodes is one step farther from node than from its parent. outside_count adds that one step for every outside node. Without it, every answer except the root's is too small. In the six-node example, node 1 gets 7 instead of 12.
Example: Sum of Distances in Tree (LC 834): n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Mistake: returns [8, 7, 4, 3, 3, 3]Fix: returns [8, 12, 6, 10, 10, 10]
Gotcha 2: Taking only down[node] out of the parent's total
Mistake
```
outside_sum = answer[parent[node]] - down[node]
```
Fix
```
outside_sum = answer[parent[node]] - down[node] - count[node]
```
What happens: answer[parent[node]] counts every node of the subtree of node at its distance from the parent. That distance is one more than its distance from node. Taking out down[node] removes the distances from node, and count[node] extra steps stay in outside_sum. Take out count[node] as well. In the six-node example, node 1 gets 13 instead of 12.
Example: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Mistake: returns [8, 13, 10, 15, 15, 15]Fix: returns [8, 12, 6, 10, 10, 10]
Gotcha 3: Running the second pass over reversed(order[1:])
Mistake
```
for node in reversed(order[1:]):
```
Fix
```
for node in order[1:]:
```
What happens: Each node needs the finished answer of its parent. order lists every parent before its children, so only the forward order has that answer ready. In the reversed order, answer[parent[node]] is still 0 when a leaf is handled. In the six-node example, nodes 3, 4 and 5 get 4 instead of 10.
Example: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Mistake: returns [8, 12, 6, 4, 4, 4]Fix: returns [8, 12, 6, 10, 10, 10]
Gotcha 4: Adding down[node] without count[node] in the first pass
Mistake
```
down[parent[node]] += down[node]
```
Fix
```
down[parent[node]] += down[node] + count[node]
```
What happens: down[node] holds distances measured from node. Seen from the parent, every node of that subtree is one step farther, and there are count[node] of them. Without count[node], every down value is too small. With n = 3 and edges = [[0,1],[0,2]], the answer for node 0 is 2, and this mistake gives 0.
Example: n = 3, edges = [[0,1],[0,2]]
Mistake: returns [0, 1, 1]Fix: returns [2, 3, 3]
Gotcha 5: Walking both passes with recursion on a long path
What happens: A path of 3 * 10^4 nodes is a valid input of Sum of Distances in Tree (LC 834). A recursive walk goes one call deeper for every node, so it goes 3 * 10^4 calls deep. Python stops at about 1000 nested calls by default and raises a RecursionError. The blueprint builds order with a loop and visits it forward and in reverse, so it has no depth limit.

Not this one if…

You need one answer for one fixed root, as in Maximum Depth of Binary Tree (LC 104): the first pass from the leaves up is enough. A question about one given node, such as All Nodes Distance K in Binary Tree (LC 863), needs each node's parent and one search from that node, not a second pass for every node. See Bottom-Up DFS
The input is an undirected tree and you need one number for the whole tree, as in Tree Diameter (LC 1245): the best value found at any node while walking up is the answer. Reroot only when the answer is a list with one entry per node. See Tree Diameter DP
Each node chooses a state that limits its children, as in House Robber III (LC 337), and the answer is for one fixed root. Several states per node answer a choice at a node. Rerooting answers a different question: which node is the root. See Tree State DP

Deep Dive

Why two neighbouring roots give almost the same answer

Some problems ask for one answer for every node, as if that node were the root. The slow way starts a new walk of the whole tree from every node. That costs N walks over N nodes each.

The first pass up and the second pass down

The trap: the outside part is part of the answer

In the six-node example, node 1 gets 7 instead of 12, and the whole answer becomes [8, 7, 4, 3, 3, 3]. Every answer except the root's is too small.

The cost, and when this card does not apply

Building order and the two passes each handle every node once. The time is O(N) and the space is O(N). The code uses no recursion, so a path of 30,000 nodes is safe.

60-Second Pitch

Common Questions

Why not run a search from every node?: That costs O(N) per node, so O(N^2) in total. With 30,000 nodes that is about 900 million steps. Rerooting reuses the answer of the parent, so each node costs O(1) after the first pass.
What does outside_count do?: It counts the nodes outside the subtree of node. Each of them is one step farther from node than from its parent, so outside_count extra steps are added to outside_sum. Without it, the answers are too small.
What if the combine step is a maximum and not a sum?: A maximum cannot be undone by subtraction. Keep the largest and the second largest value from the children of each node, and hand each child the best value that does not come through itself. Time Taken to Mark All Nodes (LC 3241) works this way.
How is this different from Tree Diameter (LC 1245)?: Tree Diameter needs one number for the whole tree, found while walking up. Rerooting needs a list with one entry per node, so it adds a second pass down.
Would a parent map and a search from one node also work?: Yes, for a question about one given node, such as All Nodes Distance K in Binary Tree (LC 863). A parent map lets the search move up as well as down. For an answer at every node, that search would repeat for every node, which costs O(N^2).

SWE Reasoning

Spot it

The problem returns a list with one answer per node, each as if that node were the root.
A walk from every node would cost O(N^2), and N is large.
The answers of two neighbouring nodes differ by a correction you can compute.
The tree is given as an edge list, so there is no fixed root.

The invariant, step by step

Root the tree at node 0 and order the nodes so that every parent comes before its children.
First pass, children before parents: count[node] and down[node] describe only the subtree of node.
The root has nothing outside its subtree, so answer[0] = down[0] is final.
Second pass, parents before children: answer[parent[node]] is final, so outside_count and outside_sum are known.
answer[node] = down[node] + outside_sum + outside_count is the answer as if node were the root, and every node is handled twice.

Traps

Leaving out outside_count. Each outside node is one step farther from node than from its parent.
Taking out only down[node]. The parent's total also holds count[node] extra steps for the subtree.
A second pass in reverse order. A child then reads a parent answer that is still 0.
Recursion on a long path. A path of 30,000 nodes passes Python's default limit, so build order with a loop.

Practice

Canonical LeetCode:Sum of Distances in Tree (LC 834)Count Number of Possible Root Nodes (LC 2581)Minimum Edge Reversals So Every Node Is Reachable (LC 2858)Time Taken to Mark All Nodes (LC 3241)

Theory Context•Depth-First Search (DFS)

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

P2HardBuilt on Bottom-Up DFS~5 min speedrun

Rerooting a Tree (Answer for Every Root)

Built on

Bottom-Up DFSA second pass walks down and hands each child the answer for everything outside its subtree, so every node gets the answer as if it were the root.

The problem

Sum of Distances in Tree (LC 834)(opens leetcode.com)

For every node i, add up the distances from node i to all other nodes. Return these n sums as a list answer, where answer[i] is the sum for node i.

The sums are independent: each node is a separate question, as if that node were the root of the tree.

Example 1

Input:n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]

Output:[8,12,6,10,10,10]

Reroot

tree ➔ first pass: subtree answers ➔ second pass: outside answers ➔ answer for every root

Reroot

Python

1	from typing import Callable, TypeVar
2
3	V = TypeVar("V")
4
5
6	def reroot(n: int, edges: list[list[int]], empty: V, lift: Callable[[V, int, int], V],
7	merge: Callable[[V, V], V], finish: Callable[[int, V], V]) -> list[V]:
8	"""Rerooting: the answer for every node, as if that node were the root of the tree.
9	lift(value, source, target) moves the value of the piece that hangs at source across
10	the edge to target.
11	merge(a, b) combines two pieces, and empty is its identity. finish(node, pieces)
12	builds the answer for node.
13	Precondition: the answer for a node depends only on the pieces that hang from it,
14	and merge is associative.
15	N = number of nodes. T = the cost of one lift, merge or finish call.
16	Time: O(N * T) \| Space: O(N)
17	"""
18	# neighbors[v] lists the nodes joined to v by an edge
19	neighbors: list[list[int]] = [[] for _ in range(n)]
20	for a, b in edges:
21	neighbors[a].append(b)
22	neighbors[b].append(a)
23
24	# 1. Order The Nodes:
25	# Root the tree at node 0. Every parent comes before its children in order, so one
26	# loop in each direction is enough.
27	parent = [-1] * n
28	order = [0]
29	for node in order:
30	for nxt in neighbors[node]:
31	if nxt != parent[node]:
32	parent[nxt] = node
33	order.append(nxt)
34
35	# 2. First Pass, Children Before Parents:
36	# down[node] is the answer for the subtree of node, built only from the answers of
37	# its children.
38	down = [empty] * n
39	for node in reversed(order):
40	pieces = empty
41	for child in neighbors[node]:
42	if child != parent[node]:
43	pieces = merge(pieces, lift(down[child], child, node))
44	down[node] = finish(node, pieces)
45
46	# 3. Second Pass, Parents Before Children:
47	# outside[child] is the answer for everything outside the subtree of child, as a
48	# tree that hangs from its parent.
49	# It merges the pieces of the parent's other children and the piece above the
50	# parent, so each child skips its own piece.
51	outside = [empty] * n
52	answer = [empty] * n
53	for node in order:
54	children = [c for c in neighbors[node] if c != parent[node]]
55	lifted = [lift(down[c], c, node) for c in children]
56	before = [empty if parent[node] < 0 else lift(outside[node], parent[node], node)]
57	for piece in lifted:
58	before.append(merge(before[-1], piece))
59	answer[node] = finish(node, before[-1])
60	after = empty
61	for i in range(len(children) - 1, -1, -1):
62	outside[children[i]] = finish(node, merge(before[i], after))
63	after = merge(lifted[i], after)
64	return answer

See it run

Sum of Distances in Tree with rerooting, step by step

Each circle is a node. The three rows under the tree show count, down and answer for every node.

node the node being handled
done a node that is already handled
total the parent, or the edge, that receives or hands down a total

The tree has 6 nodes. Node 0 is the root, and the lists count, down and answer start empty.

count

0: 1

1: 1

2: 1

3: 1

4: 1

5: 1

down

0: 0

1: 0

2: 0

3: 0

4: 0

5: 0

answer

0: ?

1: ?

2: ?

3: ?

4: ?

5: ?

1 / 14

Gotchas1 of 5

The trap
Gotcha 1: Leaving out outside_count when the root moves to node
Mistake
```
answer[node] = down[node] + outside_sum
```
Fix
```
answer[node] = down[node] + outside_sum + outside_count
```
What happens: outside_sum holds the distances from the parent to the nodes outside the subtree of node. Each of those nodes is one step farther from node than from its parent. outside_count adds that one step for every outside node. Without it, every answer except the root's is too small. In the six-node example, node 1 gets 7 instead of 12.
Example: Sum of Distances in Tree (LC 834): n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Mistake: returns [8, 7, 4, 3, 3, 3]Fix: returns [8, 12, 6, 10, 10, 10]
Gotcha 2: Taking only down[node] out of the parent's total
Mistake
```
outside_sum = answer[parent[node]] - down[node]
```
Fix
```
outside_sum = answer[parent[node]] - down[node] - count[node]
```
What happens: answer[parent[node]] counts every node of the subtree of node at its distance from the parent. That distance is one more than its distance from node. Taking out down[node] removes the distances from node, and count[node] extra steps stay in outside_sum. Take out count[node] as well. In the six-node example, node 1 gets 13 instead of 12.
Example: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Mistake: returns [8, 13, 10, 15, 15, 15]Fix: returns [8, 12, 6, 10, 10, 10]
Gotcha 3: Running the second pass over reversed(order[1:])
Mistake
```
for node in reversed(order[1:]):
```
Fix
```
for node in order[1:]:
```
What happens: Each node needs the finished answer of its parent. order lists every parent before its children, so only the forward order has that answer ready. In the reversed order, answer[parent[node]] is still 0 when a leaf is handled. In the six-node example, nodes 3, 4 and 5 get 4 instead of 10.
Example: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Mistake: returns [8, 12, 6, 4, 4, 4]Fix: returns [8, 12, 6, 10, 10, 10]
Gotcha 4: Adding down[node] without count[node] in the first pass
Mistake
```
down[parent[node]] += down[node]
```
Fix
```
down[parent[node]] += down[node] + count[node]
```
What happens: down[node] holds distances measured from node. Seen from the parent, every node of that subtree is one step farther, and there are count[node] of them. Without count[node], every down value is too small. With n = 3 and edges = [[0,1],[0,2]], the answer for node 0 is 2, and this mistake gives 0.
Example: n = 3, edges = [[0,1],[0,2]]
Mistake: returns [0, 1, 1]Fix: returns [2, 3, 3]
Gotcha 5: Walking both passes with recursion on a long path
What happens: A path of 3 * 10^4 nodes is a valid input of Sum of Distances in Tree (LC 834). A recursive walk goes one call deeper for every node, so it goes 3 * 10^4 calls deep. Python stops at about 1000 nested calls by default and raises a RecursionError. The blueprint builds order with a loop and visits it forward and in reverse, so it has no depth limit.

Not this one if…

You need one answer for one fixed root, as in Maximum Depth of Binary Tree (LC 104): the first pass from the leaves up is enough. A question about one given node, such as All Nodes Distance K in Binary Tree (LC 863), needs each node's parent and one search from that node, not a second pass for every node. See Bottom-Up DFS
The input is an undirected tree and you need one number for the whole tree, as in Tree Diameter (LC 1245): the best value found at any node while walking up is the answer. Reroot only when the answer is a list with one entry per node. See Tree Diameter DP
Each node chooses a state that limits its children, as in House Robber III (LC 337), and the answer is for one fixed root. Several states per node answer a choice at a node. Rerooting answers a different question: which node is the root. See Tree State DP

Deep Dive

Why two neighbouring roots give almost the same answer

Some problems ask for one answer for every node, as if that node were the root. The slow way starts a new walk of the whole tree from every node. That costs N walks over N nodes each.

The first pass up and the second pass down

The trap: the outside part is part of the answer

In the six-node example, node 1 gets 7 instead of 12, and the whole answer becomes [8, 7, 4, 3, 3, 3]. Every answer except the root's is too small.

The cost, and when this card does not apply

Building order and the two passes each handle every node once. The time is O(N) and the space is O(N). The code uses no recursion, so a path of 30,000 nodes is safe.

60-Second Pitch

Common Questions

Why not run a search from every node?: That costs O(N) per node, so O(N^2) in total. With 30,000 nodes that is about 900 million steps. Rerooting reuses the answer of the parent, so each node costs O(1) after the first pass.
What does outside_count do?: It counts the nodes outside the subtree of node. Each of them is one step farther from node than from its parent, so outside_count extra steps are added to outside_sum. Without it, the answers are too small.
What if the combine step is a maximum and not a sum?: A maximum cannot be undone by subtraction. Keep the largest and the second largest value from the children of each node, and hand each child the best value that does not come through itself. Time Taken to Mark All Nodes (LC 3241) works this way.
How is this different from Tree Diameter (LC 1245)?: Tree Diameter needs one number for the whole tree, found while walking up. Rerooting needs a list with one entry per node, so it adds a second pass down.
Would a parent map and a search from one node also work?: Yes, for a question about one given node, such as All Nodes Distance K in Binary Tree (LC 863). A parent map lets the search move up as well as down. For an answer at every node, that search would repeat for every node, which costs O(N^2).

SWE Reasoning

Spot it

The problem returns a list with one answer per node, each as if that node were the root.
A walk from every node would cost O(N^2), and N is large.
The answers of two neighbouring nodes differ by a correction you can compute.
The tree is given as an edge list, so there is no fixed root.

The invariant, step by step

Root the tree at node 0 and order the nodes so that every parent comes before its children.
First pass, children before parents: count[node] and down[node] describe only the subtree of node.
The root has nothing outside its subtree, so answer[0] = down[0] is final.
Second pass, parents before children: answer[parent[node]] is final, so outside_count and outside_sum are known.
answer[node] = down[node] + outside_sum + outside_count is the answer as if node were the root, and every node is handled twice.

Traps

Leaving out outside_count. Each outside node is one step farther from node than from its parent.
Taking out only down[node]. The parent's total also holds count[node] extra steps for the subtree.
A second pass in reverse order. A child then reads a parent answer that is still 0.
Recursion on a long path. A path of 30,000 nodes passes Python's default limit, so build order with a loop.

Practice

Canonical LeetCode:Sum of Distances in Tree (LC 834)Count Number of Possible Root Nodes (LC 2581)Minimum Edge Reversals So Every Node Is Reachable (LC 2858)Time Taken to Mark All Nodes (LC 3241)