Skip to main content
Back to problems
Leetcode
Medium
Graphs
Trees
Tree DP
Recursion
Google
Meta
Sum of Distances in Tree

Compute, for every node in a tree, the sum of distances to all other nodes.

Acceptance 100%
Start Practice
Also Available On
Other platform versions and source mappings for the same problem.

LeetCode 834

gfg
Primary
Problem Statement

You are given an undirected tree with nn nodes labeled from $0toton-1.Foreachnode. For each node i,determinethetotaldistancefrom, determine the total distance from i$ to every other node in the tree.

Return an array where the ii-th value is the sum of distances from node ii to all other nodes.

Because the input graph is a tree, there is exactly one simple path between any two nodes.

Input Format

  • An integer nn representing the number of nodes.
  • A list of n−1n-1 undirected edges, where each edge is a pair [u,v][u, v] connecting two nodes.

Output Format

  • Return an integer array ans of length nn.
  • ans[i] is the sum of shortest-path distances from node ii to every other node.

Constraints

  • 1≤n≤3×1041 \le n \le 3 \times 10^4
  • The graph is a tree: connected and acyclic
  • Nodes are labeled from $0toton-1$
  • Edges are undirected and contain no duplicates
Examples
Sample cases returned by the problem API.

Example 1

Input

n = 6
edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]

Output

[8,12,6,10,10,10]

Explanation

For node 0, distances to the others are 1, 1, 2, 2, and 2, for a sum of 8. Repeating this for every node gives the full array.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints
Editorial and discussion links
Concept map and variants
Sign in to unlock
Track your progress
Sign in to bookmark this problem, save notes, and manage its revision plan.
Sign in to track progress