Sum of Distances in Tree solution and explanation
Google
9 more videos on this problem
Sum of Distances in Tree | Google | Leetcode 834 | codestorywithMIKcodestorywithMIK · 44:46 · 30K views
Sum of Distances in Tree | Leetcode 834 | Live Coding session 🔥🔥🔥 🌳🌳Coding Decoded · 14:54 · 16K views
834. Sum of Distances in Tree | Tree | DP on Trees | Exploit your Parents💀Aryan Mittal · 31:34 · 13K views
LeetCode 834. Sum of Distances in TreeHappy Coding · 28:34 · 7K views
Leetcode - Sum of Distances in Tree (Python)Timothy H Chang · 12:31 · 5K views
Leetcode 834. Sum of Distances in Tree Explained with DFS Solution in O(N) timeInterviewDose · 20:30 · 4K views
[Deprecated] LeetCode 834. Sum of Distances in Tree Explanation and Solutionhappygirlzt · 14:28 · 3K views
Sum of Distances in Tree -- LeetCode 834 -- Graph -- DFS -- Detailed Explanationcodewynk · 13:21 · 3K views
Leetcode 834 - Sum of Distances in Tree (Visualise Rerooting DP)Coffee And Code In Go · 20:52 · 773 views
Sum of Distances in Tree (LeetCode 834) (DP On Tree)CodeWithARB · 52:15 · 754 views
The problem
There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.
You are given the integer n and the array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
Return an array answer of length n where answer[i] is the sum of the distances between the ith node in the tree and all other nodes.
Example 1:
Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]] Output: [8,12,6,10,10,10] Explanation: The tree is shown above. We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) equals 1 + 1 + 2 + 2 + 2 = 8. Hence, answer[0] = 8, and so on.
Example 2:
Input: n = 1, edges = [] Output: [0]
Example 3:
Input: n = 2, edges = [[1,0]] Output: [1,1]
Constraints:
1 <= n <= 3 * 104edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != bi- The given input represents a valid tree.
Approach overview
Problem Overview: Given an undirected tree with n nodes, compute the sum of distances from every node to all other nodes. The result is an array where answer[i] equals the total distance from node i to every other node in the tree.
Approach 1: Brute Force BFS/DFS from Every Node (O(n²) time, O(n) space)
The straightforward method treats each node as a starting point and runs a BFS or DFS to compute distances to all other nodes. You build an adjacency list and repeatedly traverse the tree while accumulating distance values. This guarantees correctness but performs n traversals over a structure with n-1 edges, leading to quadratic time. It works for small inputs but fails typical interview constraints where n can reach tens of thousands.
Approach 2: DFS with Two Passes (Rerooting Technique) (O(n) time, O(n) space)
The optimal solution uses two DFS passes over the tree. First pass computes two arrays: subtreeSize[node] (number of nodes in that subtree) and the distance sum from an arbitrary root (usually node 0) to all nodes below it. This traversal aggregates child results using post-order DFS from depth-first search. The second DFS "reroots" the tree: when moving the root from parent u to child v, distances to v's subtree decrease while distances to all other nodes increase. The formula ans[v] = ans[u] - subtreeSize[v] + (n - subtreeSize[v]) updates the result in constant time per edge. Since each edge is processed twice, the algorithm runs in linear time.
Approach 3: Dynamic Programming with Recursion (Rerooting DP) (O(n) time, O(n) space)
This version frames the same idea as dynamic programming on trees. The first recursion calculates DP states for each node: subtree size and distance sum within that subtree. The second recursion propagates results outward using the rerooting transition that shifts contribution counts between parent and child. Conceptually it is identical to the two-pass DFS, but the DP framing clarifies the state transition and makes the approach easier to reason about during interviews.
Recommended for interviews: The rerooting DFS solution is the expected answer. Interviewers want to see that you recognize brute force is O(n²) and optimize using subtree sizes plus rerooting to reach O(n). Implementing the two-pass DFS cleanly demonstrates strong understanding of trees, graph traversal, and dynamic programming on tree structures.
Approach 1: DFS with Two Passes
This approach involves two main DFS passes to calculate the sum of distances using subtree properties.
- Step 1: Use DFS to calculate the sum of distances for the root (typically node 0) and the subtree-node counts (the number of nodes in the subtree for each node).
- Step 2: Use the results from Step 1 to calculate the distances for all other nodes by transforming the results from the root in linear time using the parent-child relationship between nodes.
from collections import defaultdict
class Solution:
def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
res = [0] * n
count = [1] * n
def dfs1(node: int, parent: int):
for nei in graph[node]:
if nei == parent:
continue
dfs1(nei, node)
count[node] += count[nei]
res[node] += res[nei] + count[nei]
def dfs2(node: int, parent: int):
for nei in graph[node]:
if nei == parent:
continue
res[nei] = res[node] - count[nei] + (n - count[nei])
dfs2(nei, node)
dfs1(0, -1)
dfs2(0, -1)
return res#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
vector<int> res(n, 0);
vector<int> count(n, 1);
unordered_map<int, vector<int>> graph;
for (auto &e : edges) {
graph[e[0]].push_back(e[1]);
graph[e[1]].push_back(e[0]);
}
function<void(int, int)> dfs1 = [&](int node, int parent) {
for (int nei : graph[node]) {
if (nei == parent) continue;
dfs1(nei, node);
count[node] += count[nei];
res[node] += res[nei] + count[nei];
}
};
function<void(int, int)> dfs2 = [&](int node, int parent) {
for (int nei : graph[node]) {
if (nei == parent) continue;
res[nei] = res[node] - count[nei] + (n - count[nei]);
dfs2(nei, node);
}
};
dfs1(0, -1);
dfs2(0, -1);
return res;
}
};Here, we use two DFS functions:
dfs1computes the initial result for the root and counts the number of nodes in each subtree.dfs2recalculates the result for each node by reusing and adjusting the results from its parent, leveraging the relationship:res[child] = res[parent] - count[child] + (n - count[child]).
Time Complexity: O(n), Space Complexity: O(n), due to the graph representation and DFS recursion stack.
Approach 2: Dynamic Programming and Recursion
This approach uses dynamic programming principles and recursive relationships between nodes to determine distances, updating accumulated state data as we compute each node's distance sum.
import java.util.ArrayList;
import java.util.List;
public class Solution {
private int[] res, count;
private List<List<Integer>> graph;
public int[] sumOfDistancesInTree(int n, int[][] edges) {
graph = new ArrayList<>();
res = new int[n];
count = new int[n];
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
for (int[] e : edges) {
graph.get(e[0]).add(e[1]);
graph.get(e[1]).add(e[0]);
}
dfs1(0, -1);
dfs2(0, -1, n);
return res;
}
private void dfs1(int node, int parent) {
for (int nei : graph.get(node)) {
if (nei == parent) continue;
dfs1(nei, node);
count[node] += count[nei];
res[node] += res[nei] + count[nei];
}
count[node]++;
}
private void dfs2(int node, int parent, int n) {
for (int nei : graph.get(node)) {
if (nei == parent) continue;
res[nei] = res[node] - count[nei] + (n - count[nei]);
dfs2(nei, node, n);
}
}
}var sumOfDistancesInTree = function(n, edges) {
let graph = Array.from({ length: n }, () => []);
let res = Array(n).fill(0);
let count = Array(n).fill(1);
for (let [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
function dfs1(node, parent) {
for (let nei of graph[node]) {
if (nei === parent) continue;
dfs1(nei, node);
count[node] += count[nei];
res[node] += res[nei] + count[nei];
}
}
function dfs2(node, parent) {
for (let nei of graph[node]) {
if (nei === parent) continue;
res[nei] = res[node] - count[nei] + (n - count[nei]);
dfs2(nei, node);
}
}
dfs1(0, -1);
dfs2(0, -1);
return res;
};In Java, this implementation involves running two recursive functions:
dfs1aggregates initial path sums and node counts.dfs2dynamically redistributes total distances by applying the recursive relationship using parent data.
Time Complexity: O(n), Space Complexity: O(n), resulting from recursive DFS and storage of results and counts for each node.
Approach 3: Tree DP (Re-rooting)
First, we run a DFS to calculate the size of each node's subtree, recorded in the array size, and compute the sum of distances from node 0 to all other nodes, recorded in ans[0].
Next, we run another DFS to enumerate the sum of distances from each node when it is considered as the root. Suppose the answer for the current node i is t. When we move from node i to node j, the sum of distances changes to t - size[j] + n - size[j], meaning the sum of distances to node j and its subtree nodes decreases by size[j], while the sum of distances to other nodes increases by n - size[j].
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the tree.
Similar problems:
function sumOfDistancesInTree(n: number, edges: number[][]): number[] {
const g: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
g[a].push(b);
g[b].push(a);
}
const ans: number[] = new Array(n).fill(0);
const size: number[] = new Array(n).fill(0);
const dfs1 = (i: number, fa: number, d: number) => {
ans[0] += d;
size[i] = 1;
for (const j of g[i]) {
if (j !== fa) {
dfs1(j, i, d + 1);
size[i] += size[j];
}
}
};
const dfs2 = (i: number, fa: number, t: number) => {
ans[i] = t;
for (const j of g[i]) {
if (j !== fa) {
dfs2(j, i, t - size[j] + n - size[j]);
}
}
};
dfs1(0, -1, 0);
dfs2(0, -1, ans[0]);
return ans;
}func sumOfDistancesInTree(n int, edges [][]int) []int {
g := make([][]int, n)
for _, e := range edges {
a, b := e[0], e[1]
g[a] = append(g[a], b)
g[b] = append(g[b], a)
}
ans := make([]int, n)
size := make([]int, n)
var dfs1 func(i, fa, d int)
dfs1 = func(i, fa, d int) {
ans[0] += d
size[i] = 1
for _, j := range g[i] {
if j != fa {
dfs1(j, i, d+1)
size[i] += size[j]
}
}
}
var dfs2 func(i, fa, t int)
dfs2 = func(i, fa, t int) {
ans[i] = t
for _, j := range g[i] {
if j != fa {
dfs2(j, i, t-size[j]+n-size[j])
}
}
}
dfs1(0, -1, 0)
dfs2(0, -1, ans[0])
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| DFS with Two Passes | Time Complexity: O(n), Space Complexity: O(n), due to the graph representation and DFS recursion stack. |
| Dynamic Programming and Recursion | Time Complexity: O(n), Space Complexity: O(n), resulting from recursive DFS and storage of results and counts for each node. |
| Tree DP (Re-rooting) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force BFS/DFS from Each Node | O(n²) | O(n) | Good for understanding the problem or when n is very small |
| DFS with Two Passes (Rerooting) | O(n) | O(n) | Optimal interview solution for computing all node distance sums |
| Dynamic Programming with Recursion | O(n) | O(n) | Preferred when explaining rerooting as tree DP states |
Frequently asked questions
Is Sum of Distances in Tree easy or hard?
LeetCode classifies this problem as Hard because it requires recognizing the rerooting dynamic programming pattern on trees. The algorithm itself is concise once understood, but discovering the transition formula and two-pass DFS strategy can be challenging during interviews.
Sum of Distances in Tree Python/Java solution
Python and Java implementations typically use adjacency lists and two DFS functions. The first computes subtree sizes and initial distance sums, and the second propagates results using the rerooting formula. Both languages achieve O(n) time and O(n) space with recursion or iterative DFS.
How to solve Sum of Distances in Tree in O(n)?
Build an adjacency list and run a post-order DFS to compute subtree sizes and the distance sum for an initial root node. Then perform a second DFS that reroots the tree using the formula ans[v] = ans[u] - subtreeSize[v] + (n - subtreeSize[v]). This efficiently updates results for every node in linear time.
What is the best approach for Sum of Distances in Tree?
The best approach is a rerooting technique using two DFS traversals. The first DFS computes subtree sizes and the total distance sum from an initial root. The second DFS propagates results to all nodes using a constant-time transition formula. This achieves O(n) time and O(n) space.
Is Sum of Distances in Tree asked at Google/Amazon/Meta?
Tree dynamic programming and rerooting problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. The question tests understanding of DFS traversal, subtree aggregation, and efficient re-computation of global metrics when changing the root.
What data structure is used in Sum of Distances in Tree?
The problem uses an adjacency list to represent the tree graph. DFS traversal processes the structure, while arrays store subtree sizes and computed distance sums. This combination enables efficient rerooting updates in O(1) per edge.
What is the time complexity of Sum of Distances in Tree?
The optimal solution runs in O(n) time because each edge in the tree is processed a constant number of times across two DFS traversals. Space complexity is O(n) for the adjacency list, recursion stack, and arrays storing subtree sizes and distance sums.