Sum of Distances in Tree

Hard
1540.

Sum of Distances in Tree

Sum of Distances in Tree is a hard coding problem on dynamic programming, depth-first search and trees, asked in Amazon, Google and PhonePe interviews.

An undirected, connected tree has n nodes labelled 0 to n - 1 and the n - 1 edges in edges, each [ai, bi].

Return an array answer of length n where answer[i] is the sum of the distances (numbers of edges) between node i and every other node.

Example 1

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

Example 2

Input
n = 1, edges = []
Output
[0]

Example 3

Input
n = 3, edges = [[2,0],[2,1]]
Output
[3,3,2]

Constraints

  • 1 <= n <= 3 * 10^4
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • the given input represents a valid tree
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[]}
 */
var sumOfDistancesInTree = function(n, edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sum of Distances in Tree — Solution in Python, Java & C++

Sum of Distances in Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Sum of Distances in Tree is a hard coding problem on dynamic programming, depth-first search and trees, asked in Amazon, Google and PhonePe interviews.

Problem statement

An undirected, connected tree has n nodes labelled 0 to n - 1 and the n - 1 edges in edges, each [ai, bi].

Return an array answer of length n where answer[i] is the sum of the distances (numbers of edges) between node i and every other node.

Example 1

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

Example 2

Input: n = 1, edges = []
Output: [0]

Example 3

Input: n = 3, edges = [[2,0],[2,1]]
Output: [3,3,2]

Constraints

  • 1 <= n <= 3 * 10^4
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • the given input represents a valid tree

Hints for Sum of Distances in Tree

  1. Hint 1

    One BFS per node is O(n²) — too slow for 3 · 10^4 nodes. Can one node's answer be derived from its neighbour's?

  2. Hint 2

    Root the tree at 0 and compute subtree sizes. When you move the 'viewpoint' from a parent p to its child c, the nodes in c's subtree get 1 closer and all the others get 1 farther.

  3. Hint 3

    So answer[c] = answer[p] − size[c] + (n − size[c]). Compute answer[0] with one post-order pass, then fill in the rest top-down.

How to solve Sum of Distances in Tree

Re-rooting: compute the answer for the root directly, then shift the root across each edge, adjusting by how many nodes move closer and how many move farther.

Approach

  1. Root at node 0 and get a BFS order and parents.
  2. In reverse BFS order, accumulate count[u] (subtree size) and sub[u] (sum of distances from u to its subtree): count[p] += count[c], sub[p] += sub[c] + count[c].
  3. answer[0] = sub[0].
  4. In BFS order, for every child c of p: answer[c] = answer[p] − count[c] + (n − count[c]).

Why it works

Moving from p to its child c shortens the distance to each of the count[c] nodes in c's subtree by one and lengthens the distance to each of the other n − count[c] nodes by one; nothing else changes. Starting from the exact root value and applying this along every edge gives every node's exact sum.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Recursive DFS over a 3 · 10^4-node path can overflow the call stack; a BFS order avoids recursion.
  • sub[p] must add count[c] as well as sub[c] — every node of the child subtree is one edge farther from p.
  • n = 1 has no edges; the answer is [0].

Reference solution

Python

from typing import List

def sumOfDistancesInTree(n: int, edges: List[List[int]]) -> List[int]:
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    parent = [-1] * n
    seen = [False] * n
    seen[0] = True
    order = [0]
    for u in order:
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                parent[v] = u
                order.append(v)
    count = [1] * n
    sub = [0] * n
    for u in reversed(order):
        p = parent[u]
        if p >= 0:
            count[p] += count[u]
            sub[p] += sub[u] + count[u]
    ans = [0] * n
    ans[0] = sub[0]
    for u in order:
        if u != 0:
            ans[u] = ans[parent[u]] - count[u] + (n - count[u])
    return ans

Java

public static 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[] parent = new int[n], order = new int[n], count = new int[n], sub = new int[n], ans = new int[n];
    Arrays.fill(parent, -2);
    Arrays.fill(count, 1);
    parent[0] = -1;
    int tail = 0;
    order[tail++] = 0;
    for (int h = 0; h < tail; h++) {
        int u = order[h];
        for (int v : adj.get(u)) if (parent[v] == -2) { parent[v] = u; order[tail++] = v; }
    }
    for (int t = n - 1; t > 0; t--) {
        int c = order[t], p = parent[c];
        count[p] += count[c];
        sub[p] += sub[c] + count[c];
    }
    ans[0] = sub[0];
    for (int k = 1; k < n; k++) {
        int w = order[k];
        ans[w] = ans[parent[w]] - count[w] + (n - count[w]);
    }
    return ans;
}

C++

vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
    vector<int> parent(n, -2), count(n, 1), sub(n, 0), ans(n, 0), order;
    parent[0] = -1;
    order.push_back(0);
    for (size_t h = 0; h < order.size(); h++) {
        int u = order[h];
        for (int v : adj[u]) if (parent[v] == -2) { parent[v] = u; order.push_back(v); }
    }
    for (int t = n - 1; t > 0; t--) {
        int c = order[t], p = parent[c];
        count[p] += count[c];
        sub[p] += sub[c] + count[c];
    }
    ans[0] = sub[0];
    for (int k = 1; k < n; k++) {
        int w = order[k];
        ans[w] = ans[parent[w]] - count[w] + (n - count[w]);
    }
    return ans;
}

JavaScript

var sumOfDistancesInTree = function(n, edges) {
    var adj = [], parent = [], count = [], sub = [], ans = [];
    for (var i = 0; i < n; i++) { adj.push([]); parent.push(-2); count.push(1); sub.push(0); ans.push(0); }
    for (var e = 0; e < edges.length; e++) {
        adj[edges[e][0]].push(edges[e][1]);
        adj[edges[e][1]].push(edges[e][0]);
    }
    parent[0] = -1;
    var order = [0];
    for (var h = 0; h < order.length; h++) {
        var u = order[h];
        for (var j = 0; j < adj[u].length; j++) {
            var v = adj[u][j];
            if (parent[v] === -2) { parent[v] = u; order.push(v); }
        }
    }
    for (var t = n - 1; t > 0; t--) {
        var c = order[t], p = parent[c];
        count[p] += count[c];
        sub[p] += sub[c] + count[c];
    }
    ans[0] = sub[0];
    for (var k = 1; k < n; k++) {
        var w = order[k];
        ans[w] = ans[parent[w]] - count[w] + (n - count[w]);
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Depth-First Search (DFS)