Sum of Distances in Tree

LeetCode 863 | Difficulty: Hard

Hard

Problem Description

There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.

You are given the integer n and the array edges where edges[i] = [a~i~, b~i~] indicates that there is an edge between nodes a~i~ and b~i~ in the tree.

Return an array answer of length n where answer[i] is the sum of the distances between the i^th node in the tree and all other nodes.

Example 1:

Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer[0] = 8, and so on.

Example 2:

Input: n = 1, edges = []
Output: [0]

Example 3:

Input: n = 2, edges = [[1,0]]
Output: [1,1]

Constraints:

- `1 <= n <= 3 * 10^4`

- `edges.length == n - 1`

- `edges[i].length == 2`

- `0 <= a~i~, b~i~ < n`

- `a~i~ != b~i~`

- The given input represents a valid tree.

Topics: Dynamic Programming, Tree, Depth-First Search, Graph Theory

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

Tree DFS

Traverse the tree recursively (or with a stack). At each node, decide: what information do I need from the left/right subtrees? Process: go left → go right → combine results. Consider preorder, inorder, or postorder traversal based on when you need to process the node.

When to use

Path problems, subtree properties, tree structure manipulation.

Graph Traversal

Model the problem as a graph (nodes + edges). Choose BFS for shortest path or DFS for exploring all paths. For dependency ordering, use topological sort (Kahn's BFS or DFS with finish times).

When to use

Connectivity, shortest path, cycle detection, dependency ordering.

---

Solutions

Solution 1: C# (Best: 508 ms)

Metric	Value
Runtime	508 ms
Memory	57.7 MB
Date	2022-02-05

Solution

public class Solution {
    private Dictionary<int, List<int>> graph;
    private int[] result, count;
    public int[] SumOfDistancesInTree(int n, int[][] edges)
    {
        if(edges == null || edges.Length == 0) return new int[1] {0};
        graph = new Dictionary<int, List<int>>();
        foreach (var edge in edges)
        {
            if (graph.ContainsKey(edge[0])) graph[edge[0]].Add(edge[1]);
            else graph.Add(edge[0], new List<int>() { edge[1]});

            if (graph.ContainsKey(edge[1])) graph[edge[1]].Add(edge[0]);
            else graph.Add(edge[1], new List<int>() { edge[0] });
        }
        
        result = new int[n];
        count = new int[n];
        Dfs(0);
        Dfs2(0,n);
        return result;
    }
    
    private void Dfs(int i, int p=-1)
    {
        foreach (var u in graph[i])
        {
            if(u==p) continue;
            Dfs(u,i);
            count[i] += count[u];
            result[i] += result[u]+count[u];
        }
        count[i]++;
    }
    
    private void Dfs2(int i, int n, int p=-1)
    {
        foreach (var u in graph[i])
        {
            if(u==p) continue;          
            result[u] = result[i]-count[u]+n-count[u];
            Dfs2(u,n,i);
        }       
    }
}

---

Complexity Analysis

Approach	Time	Space
DP (2D)	$O(n × m)$	$O(n × m)$
Tree Traversal	$O(n)$	$O(h)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.
• Ask about graph properties: directed/undirected, weighted/unweighted, cycles, connectivity.