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.
- Difficulty: Hard
- Topics: Dynamic Programming, Depth-First Search, Trees, Graph
- Asked at: Amazon, Google, PhonePe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^4edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != bithe given input represents a valid tree
Hints for Sum of Distances in Tree
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?
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.
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
- Root at node 0 and get a BFS order and parents.
- In reverse BFS order, accumulate
count[u](subtree size) andsub[u](sum of distances fromuto its subtree):count[p] += count[c],sub[p] += sub[c] + count[c]. answer[0] = sub[0].- In BFS order, for every child
cofp: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 addcount[c]as well assub[c]— every node of the child subtree is one edge farther fromp.- 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 ansJava
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)