Sum of Distances in Tree

Hard Graphs Re-rooting DP Original on LeetCode

Reported atPhonePe

Sum of Distances in Tree is a hard graphs problem solved with the re-rooting dp pattern. The best approach, optimal (re-rooting with two passes), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (bfs from every node) up.

Problem

You are given an undirected tree with n nodes labelled 0 to n - 1, described by the list edges, where edges[i] = [a, b] is an edge between nodes a and b.

Return an array answer of length n where answer[i] is the sum of the distances (number of edges on the path) from node i to every other node in the tree.

Examples

Example 1

Input
n = 5, edges = [[0, 1], [1, 2], [1, 3], [3, 4]]
Output
[8, 5, 8, 6, 9]
Why
From node 1 the distances to 0, 2, 3, 4 are 1, 1, 1, 2, which add up to 5. From node 4 they are 3, 2, 3, 1, adding up to 9.

Example 2

Input
n = 3, edges = [[2, 0], [2, 1]]
Output
[3, 3, 2]
Why
Node 2 is the center and is one step from both others; each leaf is 1 step from the center and 2 from the other leaf.

Example 3

Input
n = 1, edges = []
Output
[0]
Why
A single node has nothing to measure against.

Constraints

  • 1 <= n <= 3 * 10^4
  • edges.length == n - 1, edges[i] = [a, b] with 0 <= a, b < n and a != b
  • The edges form a tree (connected, no cycles).

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (BFS from every node)O(n²)O(n)
Optimal (re-rooting with two passes)O(n)O(n)

1Brute force (BFS from every node)

TimeO(n²)n breadth-first searches, each visiting all n nodes and n - 1 edges.
SpaceO(n)The adjacency list, a queue and a distance array, reused for every source.

Build an adjacency list. For each node, run a BFS over the tree to get the distance to every other node, and add those distances up. In a tree, BFS distances are exactly the unique path lengths.

  1. Build the adjacency list from edges.
  2. For each source s: BFS from s, recording dist for each visited node.
  3. ans[s] = sum of all dist values.
class Solution {
    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];
        int[] queue = new int[n];
        for (int s = 0; s < n; s++) {
            Arrays.fill(dist, -1);
            dist[s] = 0;
            int head = 0, tail = 0, total = 0;
            queue[tail++] = s;
            while (head < tail) {
                int u = queue[head++];
                total += dist[u];
                for (int v : adj.get(u))
                    if (dist[v] < 0) {
                        dist[v] = dist[u] + 1;
                        queue[tail++] = v;
                    }
            }
            ans[s] = total;
        }
        return ans;
    }
}

2Optimal (re-rooting with two passes)

TimeO(n)One BFS plus two linear sweeps over the order.
SpaceO(n)Adjacency list and a handful of length-n arrays.

Root the tree at 0 and get a BFS order with parents. Walking that order backwards (children before parents) computes size[u], the number of nodes in u's subtree, and down[u], the sum of distances from u to the nodes of its subtree: down[p] += down[c] + size[c]. Then ans[0] = down[0]. Walking the BFS order forwards, each child gets ans[c] = ans[p] - size[c] + (n - size[c]), because moving the root across the edge brings its own subtree one step closer and pushes everything else one step away. Using an explicit order instead of recursion keeps long paths safe.

  1. Build the adjacency list; BFS from 0 to record order and parent.
  2. For u in reverse order (skipping the root): size[parent] += size[u]; down[parent] += down[u] + size[u].
  3. ans[0] = down[0].
  4. For u in order (skipping the root): ans[u] = ans[parent[u]] + n - 2 * size[u].
class Solution {
    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[] order = new int[n], parent = new int[n];
        boolean[] seen = new boolean[n];
        int head = 0, tail = 0;
        order[tail++] = 0;
        seen[0] = true;
        parent[0] = -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], down = new int[n];
        Arrays.fill(size, 1);
        for (int i = n - 1; i > 0; i--) {
            int u = order[i], p = parent[u];
            size[p] += size[u];
            down[p] += down[u] + size[u];
        }
        int[] ans = new int[n];
        ans[0] = down[0];
        for (int i = 1; i < n; i++) {
            int u = order[i];
            ans[u] = ans[parent[u]] + n - 2 * size[u];
        }
        return ans;
    }
}

Edge cases to test

  • A single node: the answer is [0]
  • Two nodes: both answers are 1
  • A long path, where recursion depth can reach n
  • A star, where the center has the smallest sum and every leaf the same larger sum
  • Edges given in either direction and in no particular order

Hints

Hint 1

Running a BFS from every node works but is quadratic. Can the answer for a node be derived from the answer of its neighbour?

Hint 2

Root the tree at node 0. When you move the root from a parent p to its child c, the size[c] nodes in c's subtree get one step closer and the other n - size[c] nodes get one step farther.

Hint 3

So ans[c] = ans[p] - size[c] + (n - size[c]). One post-order pass computes subtree sizes and ans[0]; one pre-order pass fills in everyone else.

FAQ

What is the best time complexity for Sum of Distances in Tree?

Optimal (re-rooting with two passes) runs in O(n) time and O(n) extra space. One BFS plus two linear sweeps over the order.

Which pattern does Sum of Distances in Tree use?

It is a graphs problem that uses the re-rooting dp pattern. Other problems with the same pattern: Minimum Edge Reversals So Every Node Is Reachable.

Is there a brute force solution for Sum of Distances in Tree?

Yes. Brute force (BFS from every node) takes O(n²) time and O(n) space. Build an adjacency list.

Which edge cases should I test for Sum of Distances in Tree?

A single node: the answer is [0]; Two nodes: both answers are 1; A long path, where recursion depth can reach n; A star, where the center has the smallest sum and every leaf the same larger sum; Edges given in either direction and in no particular order.