Sum of Distances in Tree - Video Solutions
Sum of Distances in Tree | Google | Leetcode 834 | codestorywithMIK
Sum of Distances in Tree - Video Solution
Watch 10 video solutions for Sum of Distances in Tree, a hard level problem involving Dynamic Programming, Tree, Depth-First Search. This walkthrough by codestorywithMIK has 30,261 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 * 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.
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 |