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 != biProblem 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.
This approach involves two main DFS passes to calculate the sum of distances using subtree properties.
Here, we use two DFS functions:
dfs1 computes the initial result for the root and counts the number of nodes in each subtree.dfs2 recalculates 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.
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.
In Java, this implementation involves running two recursive functions:
dfs1 aggregates initial path sums and node counts.dfs2 dynamically redistributes total distances by applying the recursive relationship using parent data.Java
JavaScript
Time Complexity: O(n), Space Complexity: O(n), resulting from recursive DFS and storage of results and counts for each node.
| 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. |
| 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 |
Sum of Distances in Tree | Google | Leetcode 834 | codestorywithMIK • codestorywithMIK • 26,807 views views
Watch 9 more video solutions →Practice Sum of Distances in Tree with our built-in code editor and test cases.
Practice on FleetCode