Sum of Distances in Tree

Sum of Distances in Tree

What is this problem about?

The "Sum of Distances in Tree" problem is a classic hard-level graph challenge. You are given an undirected connected tree with $n$ nodes. For each node $i$, you need to calculate the sum of the distances from node $i$ to all other nodes in the tree. The distance between two nodes is the number of edges on the unique path connecting them. You must return an array containing these sums for all nodes.

Why is this asked in interviews?

This problem is a favorite at top-tier companies like Google, Uber, and Microsoft because it requires a deep understanding of tree properties and dynamic programming on trees. A naive approach would involve running a Breadth-First Search (BFS) or Depth-First Search (DFS) from every node, resulting in an O(N²) solution, which is too slow for large $n$. The optimized solution uses a technique called "Re-rooting DP," which is a highly sophisticated skill that distinguishes senior-level candidates.

Algorithmic pattern used

The pattern used is Re-rooting Dynamic Programming. It involves two DFS passes:

1. Bottom-up DFS: For a fixed root (say, node 0), calculate the size of each subtree (count[i]) and the sum of distances within each subtree (res[i]).
2. Top-down DFS: Shift the root from a parent to its child. When moving the root from u to v, the distance sum changes predictably: nodes in v's subtree become one edge closer, while all other nodes become one edge further away. The formula is: res[v] = res[u] - count[v] + (N - count[v]). This allows us to compute the answer for all nodes in O(N) time.

Example explanation

Imagine a simple star tree: node 0 connected to nodes 1, 2, and 3.

• For node 0: Distances are 1 (to node 1) + 1 (to node 2) + 1 (to node 3) = 3.
• For node 1: Distance is 1 (to node 0) + 2 (to node 2) + 2 (to node 3) = 5. Using re-rooting: res[1] = res[0] - count[1] + (4 - count[1]). Since count[1] = 1 (just itself), res[1] = 3 - 1 + 3 = 5. This logic propagates through the entire tree.

Common mistakes candidates make

1. O(N²) Brute Force: Not realizing that re-rooting is possible and trying to solve for each node independently.
2. Incorrect Subtree Counting: Failing to correctly account for the size of subtrees, which is essential for the transition formula.
3. Graph Representation: Using an adjacency matrix instead of an adjacency list, which leads to excessive memory usage and slow traversals.

Interview preparation tip

Master the "Re-rooting DP" technique. It is applicable to many tree problems where you need to calculate a property for every node as if it were the root. Practice the transition formula: how does the answer for a child differ from its parent?