Sum of Distances in Tree

HardTrees · Rerooting DP🧩 Tree & Graph DP LeetCode #834 ↗Updated Oct 30, 2026

Problem

You get an undirected, connected tree with n nodes labelled 0..n-1 and its n-1 edges. For every node i, compute the sum of the distances (edge counts) from i to all other nodes, and return these sums as an array answer.

Inputn=3, edges=[[0,1],[1,2]]Output[3,2,3]

Inputn=5, edges=[[0,1],[0,2],[0,3],[3,4]]Output[5,8,8,6,9]

Inputn=1, edges=[]Output[0]

1 ≤ n ≤ 3·10⁴ · edges.length = n-1 · the edges form a valid tree

Try it yourself

Java

class Solution {
    public int[] sumOfDistancesInTree(int n, int[][] edges) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Moving the “root” across edge p→c brings the size[c] nodes of c's subtree one step closer and pushes the other n - size[c] one step away, so ans[c] = ans[p] - size[c] + (n - size[c]).

PatternTree & Graph DP

Instinct A node's best answer depends only on its children's answers - post-order DFS that returns a tiny tuple of states per node.

Memory hack Kids report up, parent decides - every subtree hands its parent a small report card, and the parent never re-reads the kids' homework.

Open the Tree & Graph DP guide →

Approaches

Brute ForceBFS from Every Node

Time O(n²)Space O(n)

A tree is unweighted, so one BFS from s yields the exact distance from s to every node. Repeat it with each node as the source and add up the distances.

Java

public int[] sumOfDistancesInTree(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    int[] ans = new int[n];
    int[] dist = new int[n];
    ArrayDeque<Integer> queue = new ArrayDeque<>();
    for (int s = 0; s < n; s++) {
        Arrays.fill(dist, -1);
        dist[s] = 0;
        queue.offer(s);
        while (!queue.isEmpty()) {
            int u = queue.poll();
            ans[s] += dist[u];
            for (int v : adj.get(u)) {
                if (dist[v] < 0) {
                    dist[v] = dist[u] + 1;
                    queue.offer(v);
                }
            }
        }
    }
    return ans;
}

Obviously correct, but ~9·10⁸ steps at n = 3·10⁴ — too slow.

OptimalRerooting: Subtree Sizes, then Shift the Root

Time O(n)Space O(n)

Root the tree at 0. A bottom-up pass computes size[u] and down[u] (distance sum inside u's subtree), giving ans[0] = down[0]. A top-down pass then derives every child from its parent with the rerooting formula. Both passes walk a BFS order, so no recursion is needed even for a 30 000-node path.

Java

public int[] sumOfDistancesInTree(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    // BFS order from root 0: parents always appear before their children
    int[] order = new int[n], parent = new int[n];
    Arrays.fill(parent, -1);
    boolean[] seen = new boolean[n];
    seen[0] = true;
    int head = 0, tail = 1;
    while (head < tail) {
        int u = order[head++];
        for (int v : adj.get(u)) {
            if (!seen[v]) {
                seen[v] = true;
                parent[v] = u;
                order[tail++] = v;
            }
        }
    }
    int[] size = new int[n];
    int[] down = new int[n]; // sum of distances from u to nodes in its subtree
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i];
        size[u] += 1;
        if (parent[u] >= 0) {
            size[parent[u]] += size[u];
            down[parent[u]] += down[u] + size[u];
        }
    }
    int[] ans = new int[n];
    ans[0] = down[0];
    for (int i = 1; i < n; i++) {
        int c = order[i];
        ans[c] = ans[parent[c]] - size[c] + (n - size[c]);
    }
    return ans;
}

Two linear sweeps reuse the parent's answer instead of recomputing from scratch.

Pro tip

Memorise the shift: subtree gets closer, everyone else gets farther — the same rerooting trick powers many “answer for every root” tasks.

At a glance

Level	Approach	Time	Space
Brute Force	BFS from Every Node	`O(n²)`	`O(n)`
Optimal	Rerooting: Subtree Sizes, then Shift the Root	`O(n)`	`O(n)`

Common pitfalls

Recursive DFS on a 3·10⁴-node path can overflow the default stack — use an explicit order.
Forgetting the + size[u] term: each node in the child subtree is one edge farther from the parent.
Using n - 2·size[c] with the wrong sign — derive it, don't memorise blindly.

Interview tips

Start with n BFS runs, state O(n²), then ask how a neighbour's answer relates to yours.
Draw the edge p–c splitting the tree into two parts of sizes size[c] and n-size[c].
Name the technique: “rerooting DP” — one post-order, one pre-order pass.

Pattern

Rerooting DP → when a tree question asks for an answer for every node as root.

My notes saved in this browser