Skip to main content
Talentd

Sum of Distances in Tree - Solution & Explanation

HardDynamic ProgrammingTreeDepth-First SearchGraph14 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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 * 104
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != 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.

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]).

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n), Space Complexity: O(n), due to the graph representation and DFS recursion stack.

Try this approach in the editor →

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.

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(n), Space Complexity: O(n), resulting from recursive DFS and storage of results and counts for each node.

Try this approach in the editor →

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:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force BFS/DFS from Each NodeO(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 RecursionO(n)O(n)Preferred when explaining rerooting as tree DP states

Video Solution

Sum of Distances in Tree | Google | Leetcode 834 | codestorywithMIK • codestorywithMIK • 30,261 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Sum of Distances in Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Collect Coins in a Tree

Next

Count Nodes With the Highest Score