Sum of Distances in Tree
01 · Problem
You are given an undirected, connected tree with n nodes labelled 0 to n - 1 and n - 1 edges, where edges[i] = [a_i, b_i] connects nodes a_i and b_i.
The distance between two nodes is the number of edges on the path between them. Return an array answer of length n where answer[i] is the sum of the distances from node i to every other node.
02 · Examples
n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
[8,12,6,10,10,10]
For node 0 the distances to nodes 1..5 are 1, 1, 2, 2, 2, which sum to 8. The other entries are computed the same way.
n = 1, edges = []
[0]
A single node has no other nodes to reach.
n = 3, edges = [[0,1],[1,2]]
[3,2,3]
The middle node 1 is one step from both ends (total 2); each end is 1 + 2 = 3 away from the others.
03 · Constraints
- 011 <= n <= 3 * 104
- 02edges.length == n - 1
- 03edges[i].length == 2
- 040 <= a_i, b_i < n and a_i != b_i
- 05The given edges form a valid tree.
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.