Sum of Distances in Tree
Last Updated: March 28, 2026
Understanding the Problem
We have an unweighted tree with n nodes, and we need to compute, for every node, the total distance to all other nodes. If you think about it naively, you could run a BFS from each node to find distances to every other node. But with n up to 30,000, that O(n^2) approach is going to be tight.
The real question is: can we compute the answer for all nodes without starting from scratch each time? If we already know the answer for one node, can we figure out the answer for its neighbor cheaply? That idea of "rerooting" the tree, computing the answer at one root and then shifting it to adjacent nodes, is the core technique here.
Key Constraints:
1 <= n <= 3 * 10^4→ With n up to 30,000, O(n^2) gives about 900 million operations. That is borderline and likely too slow for strict time limits. We need O(n) or O(n log n).edges.length == n - 1→ Confirms this is a tree (connected, no cycles). Every pair of nodes has exactly one path between them.- The tree is unweighted, so distance equals the number of edges on the path.
Approach 1: BFS from Every Node
Intuition
The most direct way to solve this: for each node, run a BFS (or DFS) to compute the distance to every other node. Sum those distances. Repeat for all n nodes.
This is simple to implement and easy to reason about. For each node, BFS visits every other node exactly once, giving us the total distance in O(n). Doing this for all n nodes is O(n^2).
Algorithm
- Build an adjacency list from the edges.
- For each node
ifrom 0 to n-1: - Run BFS starting from node
i. - Sum up the distances to all other nodes.
- Store the sum in
answer[i]. - Return the answer array.
Example Walkthrough
Code
- Time Complexity: O(n^2). We run BFS n times, and each BFS visits all n nodes. Total work is O(n * n) = O(n^2).
- Space Complexity: O(n). The adjacency list takes O(n) space (since there are n-1 edges). Each BFS uses O(n) for the dist, visited arrays, and queue.
We run a full BFS from every single node, completely ignoring the work done by previous runs. The distance sums for neighboring nodes are closely related, so what if we computed the answer for one root, then figured out how it changes when we shift the root to a neighbor?
Approach 2: Rerooting DP (Optimal)
Intuition
Here is the key insight that makes this problem elegant. Suppose we already know answer[p], the sum of distances from some parent node p. Now consider one of p's children c. When we move the "center" from p to c, what happens to the distances?
Every node in c's subtree gets 1 unit closer (because we moved toward them). Every node outside c's subtree gets 1 unit farther (because we moved away from them). If count[c] is the number of nodes in c's subtree, then:
count[c]nodes each get 1 closer, so distance decreases bycount[c]n - count[c]nodes each get 1 farther, so distance increases byn - count[c]
That gives us: answer[c] = answer[p] + n - 2 * count[c]
Once we know the answer for the root, we can compute the answer for every other node in O(1) per node. The whole algorithm runs in O(n).
The rerooting technique works because of a simple observation about trees: moving the root from a node to its neighbor changes every distance by exactly +1 or -1, nothing else. When you move from parent p to child c, every node in c's subtree is now 1 closer (you moved toward them), and every node outside c's subtree is now 1 farther (you moved away from them).
The subtree size is the key piece of information: it tells you exactly how many nodes benefit (get closer) and how many suffer (get farther) from each rerooting step. Since this split is always clean in a tree, the formula works perfectly.
Algorithm
- Build an adjacency list from the edges.
- DFS 1 (Post-order): Root the tree at node 0. Compute
count[i](number of nodes in the subtree rooted ati) andanswer[0](sum of distances from node 0 to all other nodes). - For each node,
count[node] = 1 + sum(count[child])for all children. - For the root,
answer[0] = sum of all depths(computed during the DFS). - DFS 2 (Pre-order): Propagate the answer from parent to child using the rerooting formula.
- For each child
cof parentp:answer[c] = answer[p] + n - 2 * count[c]. - Return the answer array.
Example Walkthrough
Code
- Time Complexity: O(n). Building the adjacency list takes O(n) (there are n-1 edges). DFS 1 visits each node once: O(n). DFS 2 visits each node once: O(n). Total: O(n).
- Space Complexity: O(n). The adjacency list, count array, answer array, parent array, order array, and visited array each take O(n) space.