Sum of Distances in Tree

HardGraphstree dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an undirected, connected tree with n nodes labeled 0 to n - 1 and n - 1 edges, where edges[i] = [a, b] joins nodes a and b. Return an array answer of length n in which answer[i] is the sum of the distances (number of edges on the shortest path) from node i to every other node in the tree. Running a BFS from every node costs O(n^2), which is too slow for the largest inputs. Solve it in O(n) by rerooting: compute subtree sizes and the answer for one root, then derive each child's answer from its parent's.

Examples

Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
From node 0 the distances are 1,1,2,2,2, which add to 8. The other entries are computed the same way.
Input: n = 1, edges = []
Output: [0]
A single node has no other nodes to reach.
Input: n = 2, edges = [[1,0]]
Output: [1,1]
Each node is one edge from the other.

Constraints

  • 1 <= n <= 3 * 10^4
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= a, b < n and a != b
  • The edges form a valid tree

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More tree dp problems