Design Gurus Logo
Sum of Distances in Tree (hard)

Problem Statement

You are given an undirected connected tree with n nodes marked from 0 to n - 1 and n - 1 edges.

You are given an integer n and the array edges where edges[i] = [ai, bi] represents that there is an edge between nodes ai and bi in the tree,

Calculate the total distance from each node to all other nodes in the tree and return these sums in an array, where the i<sup>th</sup> element corresponds to the total distance from node i.

Examples

Example 1:

  • Input: n = 4, edges = [[0, 1], [1, 2], [1, 3]]
Image
  • Expected Output: [5, 3, 5, 5]
  • Justification: From node 0, the distances to the other nodes are 1 (to node 1), 2 (to node 2), and 3 (to node 3), summing to 6. For node 1, the distance to all nodes is 1, summing to 3. Nodes 2 and 3 have the same distance profile as node 0.

Example 2:

  • Input: n = 3, edges = [[0, 1], [1, 2]]
Image
  • Expected Output: [3, 2, 3]
  • Justification: Node 0 has a total distance of 1 (to node 1) + 2 (to node 2) = 3. Node 1 is centrally located, so its total distance is 1 (to node 0) + 1 (to node 2) = 2. Node 2 has the same total distance as node 0.

Example 3:

  • Input: n = 5, edges = [[0, 2], [0, 3], [1, 3], [2, 4]]
Image
  • Expected Output: [6, 10, 7, 7, 10]
  • Justification: The tree diagram shows the distance from each node to other nodes. By summing the distance from each node to other nodes, we can get the answer.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Unlock this and all other premium problems.
No code editor for this lesson
This lesson focuses on concepts and theory