Sum of Distances in Tree (LeetCode 834)
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.
Worked Examples
n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]][8,12,6,10,10,10]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.n = 1, edges = [][0]0.n = 2, edges = [[1,0]][1,1]1.⚖️Formal Constraints & Bounds
1 <= n <= 3 * 104edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biThe given input represents a valid tree.
Core Insight
Moving the root across one edge changes the distance of every node by exactly one step: the nodes on the new root's side get one step closer, and the nodes on the other side get one step farther. So answer[node] follows from answer[parent[node]] with count[node] and down[node], and no node needs a new walk of the whole tree.
Real-World Scenario & Production Applications
A company wants to place a warehouse in one of its cities. The cities are joined by roads that form a tree, and every other city is served from the warehouse. The best city is the one with the smallest total distance to all the others. To compare the cities, you need this total for every city, not for one city.
Step-by-Step Execution Trace Table
Example 1, n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]. Walking from node 0 gives order = [0, 1, 2, 3, 4, 5] and parent = [-1, 0, 0, 2, 2, 2].
First pass (for node in reversed(order)): each node adds itself to its parent's count and its subtree's distances to its parent's down.
| Step | node | count[parent] after | down[parent] after | What it means |
|---|---|---|---|---|
| 1 | 5 | count[2] = 2 | down[2] = 1 | Node 5 is 1 step below node 2 |
| 2 | 4 | count[2] = 3 | down[2] = 2 | Node 4 is 1 step below node 2 |
| 3 | 3 | count[2] = 4 | down[2] = 3 | Node 3 is 1 step below node 2 |
| 4 | 2 | count[0] = 5 | down[0] = 7 | The 4 nodes of the subtree of node 2 are 3 + 4 = 7 steps below node 0 |
| 5 | 1 | count[0] = 6 | down[0] = 8 | Node 1 adds 1 step, so answer[0] = down[0] = 8 |
Second pass (for node in order[1:]): outside_count = n - count[node], outside_sum = answer[parent[node]] - down[node] - count[node] and answer[node] = down[node] + outside_sum + outside_count.
| Step | node | outside_count | outside_sum | answer[node] | What it means |
|---|---|---|---|---|---|
| 6 | 1 | 5 | 7 | 12 | 0 + 7 + 5: the 5 nodes outside are each 1 step farther than from node 0 |
| 7 | 2 | 2 | 1 | 6 | 3 + 1 + 2: the subtree part is 3, the outside part is node 0 and node 1 |
| 8 | 3 | 5 | 5 | 10 | 0 + 5 + 5, with outside_sum = 6 - 0 - 1 |
| 9 | 4 | 5 | 5 | 10 | Same as node 3 |
| 10 | 5 | 5 | 5 | 10 | Same as node 3 |
The result is [8, 12, 6, 10, 10, 10]. Leaving out outside_count would give [8, 7, 4, 3, 3, 3].
n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]][8,12,6,10,10,10]Example 1, n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]. Walking from node 0 gives order = [0, 1, 2, 3, 4, 5] and parent = [-1, 0, 0, 2, 2, 2].
First pass (for node in reversed(order)): each node adds itself to its parent's count and its subtree's distances to its parent's down.
| Step | node | count[parent] after | down[parent] after | What it means |
|---|---|---|---|---|
| 1 | 5 | count[2] = 2 | down[2] = 1 | Node 5 is 1 step below node 2 |
| 2 | 4 | count[2] = 3 | down[2] = 2 | Node 4 is 1 step below node 2 |
| 3 | 3 | count[2] = 4 | down[2] = 3 | Node 3 is 1 step below node 2 |
| 4 | 2 | count[0] = 5 | down[0] = 7 | The 4 nodes of the subtree of node 2 are 3 + 4 = 7 steps below node 0 |
| 5 | 1 | count[0] = 6 | down[0] = 8 | Node 1 adds 1 step, so answer[0] = down[0] = 8 |
Second pass (for node in order[1:]): outside_count = n - count[node], outside_sum = answer[parent[node]] - down[node] - count[node] and answer[node] = down[node] + outside_sum + outside_count.
| Step | node | outside_count | outside_sum | answer[node] | What it means |
|---|---|---|---|---|---|
| 6 | 1 | 5 | 7 | 12 | 0 + 7 + 5: the 5 nodes outside are each 1 step farther than from node 0 |
| 7 | 2 | 2 | 1 | 6 | 3 + 1 + 2: the subtree part is 3, the outside part is node 0 and node 1 |
| 8 | 3 | 5 | 5 | 10 | 0 + 5 + 5, with outside_sum = 6 - 0 - 1 |
| 9 | 4 | 5 | 5 | 10 | Same as node 3 |
| 10 | 5 | 5 | 5 | 10 | Same as node 3 |
The result is [8, 12, 6, 10, 10, 10]. Leaving out outside_count would give [8, 7, 4, 3, 3, 3].
| 1 | Solve the tree once with node 0 as the root, then change the answer by a small amount across each edge instead of starting a new walk from every node. |
| 2 | First pass, `for node in reversed(order)`: `count[parent[node]] += count[node]` and `down[parent[node]] += down[node] + count[node]`. |
| 3 | Second pass, `for node in order[1:]`: `outside_count = n - count[node]`, `outside_sum = answer[parent[node]] - down[node] - count[node]`, then `answer[node] = down[node] + outside_sum + outside_count`. |
| 4 | The trap: `outside_count` is part of the answer. Without it, node 1 of `n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]` gets `7` instead of `12`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Some problems ask for one answer for every node, as if that node were the root of the tree. The sum of the distances from a node to all other nodes is one example. The slow way starts a new walk of the whole tree from every node. That is N walks over N nodes each.
Two neighbouring roots give almost the same tree. When the root moves across one edge, only the nodes on the two sides of that edge change their distance, and every one of them changes by exactly one step. So the tree is solved once, with node 0 as the root, and each other node gets its answer by a small change to the answer of its parent.
📚 The Analogy: A Company With A Head Office
A company has offices joined in a tree, and one office is the head office. Every office reports two numbers to its manager: how many offices work below it, and how far away they are in total. That is the first pass, from the bottom up.
Now an office wants the same numbers as if it were the head office. It already knows its own part, the offices below it. Its manager knows everything else. So the manager hands down the numbers for the rest of the company, and the office adds one step for every office in that rest. That is the second pass, from the top down.
🔑 Why It Works
The first pass is a walk from the leaves up, the same walk as in Bottom-Up DFS. count[node] is the number of nodes in the subtree of node, and down[node] is the sum of their distances from node. Each parent adds the pieces of its children, and each node of a child's subtree is one step farther from the parent, so down[parent[node]] += down[node] + count[node].
The second pass is a walk 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 nodes outside the subtree of node number outside_count = n - count[node]. Their distances from the parent are outside_sum = answer[parent[node]] - down[node] - count[node]. From node each of them is one step farther, so answer[node] = down[node] + outside_sum + outside_count.
Every node is handled once in each pass, so the work is O(N) and no node starts a new walk of the whole tree.
Leaving out
outside_countwhen the root moves tonodeTaking only
down[node]out of the parent's totalRunning the second pass over
reversed(order[1:])Adding
down[node]withoutcount[node]in the first passWalking both passes with recursion on a long path
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"For each node i, report the total of its distances to every other node" asks for one answer per node, each as if that node were the root. A walk from every node costs O(N^2), and N can be 30,000. The answers of two neighbouring nodes differ by a small amount, so the tree is solved once and the answer is moved across each edge. This is Rerooting.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After the first pass, count[node] is the size of the subtree of node and down[node] is the sum of the distances from node to the nodes in it. When the second pass reaches node, answer[parent[node]] is final. The outside_count = n - count[node] nodes outside the subtree of node are at outside_sum in total from the parent, and each is one step farther from node. So answer[node] = down[node] + outside_sum + outside_count.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap:
answer[node] = down[node] + outside_sum + outside_count. Withoutoutside_count, the six-node example gives[8, 7, 4, 3, 3, 3]instead of[8, 12, 6, 10, 10, 10].outside_sum = answer[parent[node]] - down[node] - count[node]: taking out onlydown[node]leavescount[node]extra steps in the outside part, and node 1 of the six-node example gets13instead of12.for node in order[1:], neverreversed(order[1:]): a child needs the finished answer of its parent, and in reverse order that answer is still0.n = 1, edges = []:order = [0], the second pass has no node to handle, andanswer = [down[0]] = [0]. Code that readsedges[0]fails on this input.A path of 30,000 nodes is a valid input. A recursive walk goes 30,000 calls deep and raises RecursionError in Python, so
orderis built with a loop.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Rerooting. A walk from every node costs N times N, which is too slow for 30,000 nodes. So I root the tree at node 0 and order the nodes so that every parent comes before its children. In the first pass, from the leaves up, each node learns the size of its subtree and the sum of its distances to the nodes below it. Every node of a child's subtree is one step farther from the parent, so the parent adds the child's sum plus the child's size. Node 0 now has its final answer. In the 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. That gives each node its answer as if it were the root. Each node is handled twice, so the time is
O(N)and the space isO(N).
Complexity & Mathematical Proof
O(N)
Look at the code: the loop over order scans each node's neighbors once, so building order visits each of the N nodes and each of the N - 1 edges (twice, once from each end). The first pass handles each node once with O(1) work. The second pass handles each node once with O(1) work. Three loops of O(N) work each give O(N).
O(N)
The lists neighbors, parent, order, count, down and answer each hold N values (neighbors holds 2 * (N - 1) entries in total). No recursion is used, so there is no call stack. The extra space is O(N), and answer is also the output.
Derivation Progression
N + 2E steps
The loop over order visits each node once and looks at each edge from both of its ends.
N updates
count[parent[node]] += count[node] and down[parent[node]] += down[node] + count[node] run once for each node.
N - 1 updates
outside_count, outside_sum and answer[node] are three O(1) formulas for each node except node 0.
O(N)
Three loops of O(N) work each; no node starts a new walk of the tree.
Variable Definitions
Number of nodes in the tree (up to 30,000 here)
Number of edges, always N - 1 in a tree
Memory Architecture & Bounds
O(1): iterative, no recursion
O(N): neighbors, parent, order, count and down
O(N): the returned list answer
Boundary Best / Worst Cases
: both passes visit every node, whatever the shape of the tree
time and space
time and space, for a path or a star as well
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "for each node i, add up its distances to every other node", "one result per node, in a list of length n". One answer for every node, each as if that node were the root: Rerooting, which solves the tree once and then moves the answer across each edge.
. A walk from every node costs , about steps at the limit. Rerooting costs time and memory. The largest sum is about , which is on a path of nodes, so a 32-bit integer is enough.
A path of nodes is levels deep: a recursive walk can overflow a small call stack, so order is built with a loop. The two passes read a tree that must not change between them: if an edge is added or removed after the first pass, count and down are out of date.
Sum of Distances in Tree (LeetCode 834)
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.
Worked Examples
n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]][8,12,6,10,10,10]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.n = 1, edges = [][0]0.n = 2, edges = [[1,0]][1,1]1.⚖️Formal Constraints & Bounds
1 <= n <= 3 * 104edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biThe given input represents a valid tree.
Core Insight
Moving the root across one edge changes the distance of every node by exactly one step: the nodes on the new root's side get one step closer, and the nodes on the other side get one step farther. So answer[node] follows from answer[parent[node]] with count[node] and down[node], and no node needs a new walk of the whole tree.
Real-World Scenario & Production Applications
A company wants to place a warehouse in one of its cities. The cities are joined by roads that form a tree, and every other city is served from the warehouse. The best city is the one with the smallest total distance to all the others. To compare the cities, you need this total for every city, not for one city.
Step-by-Step Execution Trace Table
Example 1, n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]. Walking from node 0 gives order = [0, 1, 2, 3, 4, 5] and parent = [-1, 0, 0, 2, 2, 2].
First pass (for node in reversed(order)): each node adds itself to its parent's count and its subtree's distances to its parent's down.
| Step | node | count[parent] after | down[parent] after | What it means |
|---|---|---|---|---|
| 1 | 5 | count[2] = 2 | down[2] = 1 | Node 5 is 1 step below node 2 |
| 2 | 4 | count[2] = 3 | down[2] = 2 | Node 4 is 1 step below node 2 |
| 3 | 3 | count[2] = 4 | down[2] = 3 | Node 3 is 1 step below node 2 |
| 4 | 2 | count[0] = 5 | down[0] = 7 | The 4 nodes of the subtree of node 2 are 3 + 4 = 7 steps below node 0 |
| 5 | 1 | count[0] = 6 | down[0] = 8 | Node 1 adds 1 step, so answer[0] = down[0] = 8 |
Second pass (for node in order[1:]): outside_count = n - count[node], outside_sum = answer[parent[node]] - down[node] - count[node] and answer[node] = down[node] + outside_sum + outside_count.
| Step | node | outside_count | outside_sum | answer[node] | What it means |
|---|---|---|---|---|---|
| 6 | 1 | 5 | 7 | 12 | 0 + 7 + 5: the 5 nodes outside are each 1 step farther than from node 0 |
| 7 | 2 | 2 | 1 | 6 | 3 + 1 + 2: the subtree part is 3, the outside part is node 0 and node 1 |
| 8 | 3 | 5 | 5 | 10 | 0 + 5 + 5, with outside_sum = 6 - 0 - 1 |
| 9 | 4 | 5 | 5 | 10 | Same as node 3 |
| 10 | 5 | 5 | 5 | 10 | Same as node 3 |
The result is [8, 12, 6, 10, 10, 10]. Leaving out outside_count would give [8, 7, 4, 3, 3, 3].
n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]][8,12,6,10,10,10]Example 1, n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]. Walking from node 0 gives order = [0, 1, 2, 3, 4, 5] and parent = [-1, 0, 0, 2, 2, 2].
First pass (for node in reversed(order)): each node adds itself to its parent's count and its subtree's distances to its parent's down.
| Step | node | count[parent] after | down[parent] after | What it means |
|---|---|---|---|---|
| 1 | 5 | count[2] = 2 | down[2] = 1 | Node 5 is 1 step below node 2 |
| 2 | 4 | count[2] = 3 | down[2] = 2 | Node 4 is 1 step below node 2 |
| 3 | 3 | count[2] = 4 | down[2] = 3 | Node 3 is 1 step below node 2 |
| 4 | 2 | count[0] = 5 | down[0] = 7 | The 4 nodes of the subtree of node 2 are 3 + 4 = 7 steps below node 0 |
| 5 | 1 | count[0] = 6 | down[0] = 8 | Node 1 adds 1 step, so answer[0] = down[0] = 8 |
Second pass (for node in order[1:]): outside_count = n - count[node], outside_sum = answer[parent[node]] - down[node] - count[node] and answer[node] = down[node] + outside_sum + outside_count.
| Step | node | outside_count | outside_sum | answer[node] | What it means |
|---|---|---|---|---|---|
| 6 | 1 | 5 | 7 | 12 | 0 + 7 + 5: the 5 nodes outside are each 1 step farther than from node 0 |
| 7 | 2 | 2 | 1 | 6 | 3 + 1 + 2: the subtree part is 3, the outside part is node 0 and node 1 |
| 8 | 3 | 5 | 5 | 10 | 0 + 5 + 5, with outside_sum = 6 - 0 - 1 |
| 9 | 4 | 5 | 5 | 10 | Same as node 3 |
| 10 | 5 | 5 | 5 | 10 | Same as node 3 |
The result is [8, 12, 6, 10, 10, 10]. Leaving out outside_count would give [8, 7, 4, 3, 3, 3].
| 1 | Solve the tree once with node 0 as the root, then change the answer by a small amount across each edge instead of starting a new walk from every node. |
| 2 | First pass, `for node in reversed(order)`: `count[parent[node]] += count[node]` and `down[parent[node]] += down[node] + count[node]`. |
| 3 | Second pass, `for node in order[1:]`: `outside_count = n - count[node]`, `outside_sum = answer[parent[node]] - down[node] - count[node]`, then `answer[node] = down[node] + outside_sum + outside_count`. |
| 4 | The trap: `outside_count` is part of the answer. Without it, node 1 of `n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]` gets `7` instead of `12`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Some problems ask for one answer for every node, as if that node were the root of the tree. The sum of the distances from a node to all other nodes is one example. The slow way starts a new walk of the whole tree from every node. That is N walks over N nodes each.
Two neighbouring roots give almost the same tree. When the root moves across one edge, only the nodes on the two sides of that edge change their distance, and every one of them changes by exactly one step. So the tree is solved once, with node 0 as the root, and each other node gets its answer by a small change to the answer of its parent.
📚 The Analogy: A Company With A Head Office
A company has offices joined in a tree, and one office is the head office. Every office reports two numbers to its manager: how many offices work below it, and how far away they are in total. That is the first pass, from the bottom up.
Now an office wants the same numbers as if it were the head office. It already knows its own part, the offices below it. Its manager knows everything else. So the manager hands down the numbers for the rest of the company, and the office adds one step for every office in that rest. That is the second pass, from the top down.
🔑 Why It Works
The first pass is a walk from the leaves up, the same walk as in Bottom-Up DFS. count[node] is the number of nodes in the subtree of node, and down[node] is the sum of their distances from node. Each parent adds the pieces of its children, and each node of a child's subtree is one step farther from the parent, so down[parent[node]] += down[node] + count[node].
The second pass is a walk 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 nodes outside the subtree of node number outside_count = n - count[node]. Their distances from the parent are outside_sum = answer[parent[node]] - down[node] - count[node]. From node each of them is one step farther, so answer[node] = down[node] + outside_sum + outside_count.
Every node is handled once in each pass, so the work is O(N) and no node starts a new walk of the whole tree.
Leaving out
outside_countwhen the root moves tonodeTaking only
down[node]out of the parent's totalRunning the second pass over
reversed(order[1:])Adding
down[node]withoutcount[node]in the first passWalking both passes with recursion on a long path
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"For each node i, report the total of its distances to every other node" asks for one answer per node, each as if that node were the root. A walk from every node costs O(N^2), and N can be 30,000. The answers of two neighbouring nodes differ by a small amount, so the tree is solved once and the answer is moved across each edge. This is Rerooting.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After the first pass, count[node] is the size of the subtree of node and down[node] is the sum of the distances from node to the nodes in it. When the second pass reaches node, answer[parent[node]] is final. The outside_count = n - count[node] nodes outside the subtree of node are at outside_sum in total from the parent, and each is one step farther from node. So answer[node] = down[node] + outside_sum + outside_count.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap:
answer[node] = down[node] + outside_sum + outside_count. Withoutoutside_count, the six-node example gives[8, 7, 4, 3, 3, 3]instead of[8, 12, 6, 10, 10, 10].outside_sum = answer[parent[node]] - down[node] - count[node]: taking out onlydown[node]leavescount[node]extra steps in the outside part, and node 1 of the six-node example gets13instead of12.for node in order[1:], neverreversed(order[1:]): a child needs the finished answer of its parent, and in reverse order that answer is still0.n = 1, edges = []:order = [0], the second pass has no node to handle, andanswer = [down[0]] = [0]. Code that readsedges[0]fails on this input.A path of 30,000 nodes is a valid input. A recursive walk goes 30,000 calls deep and raises RecursionError in Python, so
orderis built with a loop.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Rerooting. A walk from every node costs N times N, which is too slow for 30,000 nodes. So I root the tree at node 0 and order the nodes so that every parent comes before its children. In the first pass, from the leaves up, each node learns the size of its subtree and the sum of its distances to the nodes below it. Every node of a child's subtree is one step farther from the parent, so the parent adds the child's sum plus the child's size. Node 0 now has its final answer. In the 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. That gives each node its answer as if it were the root. Each node is handled twice, so the time is
O(N)and the space isO(N).
Complexity & Mathematical Proof
O(N)
Look at the code: the loop over order scans each node's neighbors once, so building order visits each of the N nodes and each of the N - 1 edges (twice, once from each end). The first pass handles each node once with O(1) work. The second pass handles each node once with O(1) work. Three loops of O(N) work each give O(N).
O(N)
The lists neighbors, parent, order, count, down and answer each hold N values (neighbors holds 2 * (N - 1) entries in total). No recursion is used, so there is no call stack. The extra space is O(N), and answer is also the output.
Derivation Progression
N + 2E steps
The loop over order visits each node once and looks at each edge from both of its ends.
N updates
count[parent[node]] += count[node] and down[parent[node]] += down[node] + count[node] run once for each node.
N - 1 updates
outside_count, outside_sum and answer[node] are three O(1) formulas for each node except node 0.
O(N)
Three loops of O(N) work each; no node starts a new walk of the tree.
Variable Definitions
Number of nodes in the tree (up to 30,000 here)
Number of edges, always N - 1 in a tree
Memory Architecture & Bounds
O(1): iterative, no recursion
O(N): neighbors, parent, order, count and down
O(N): the returned list answer
Boundary Best / Worst Cases
: both passes visit every node, whatever the shape of the tree
time and space
time and space, for a path or a star as well
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "for each node i, add up its distances to every other node", "one result per node, in a list of length n". One answer for every node, each as if that node were the root: Rerooting, which solves the tree once and then moves the answer across each edge.
. A walk from every node costs , about steps at the limit. Rerooting costs time and memory. The largest sum is about , which is on a path of nodes, so a 32-bit integer is enough.
A path of nodes is levels deep: a recursive walk can overflow a small call stack, so order is built with a loop. The two passes read a tree that must not change between them: if an edge is added or removed after the first pass, count and down are out of date.