#834

Hard

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Sum of Distances in Tree

The problem asks to compute the sum of distances between each node and all others in a tree structure using depth-first search.

dynamic programming tree depth first search graph

Problem Statement

You are given a tree with n nodes labeled from 0 to n-1 and n-1 edges. The tree is connected and undirected. An edge between nodes ai and bi is represented by edges[i] = [ai, bi].

The goal is to compute an array answer of length n, where each answer[i] represents the sum of the distances between node i and all other nodes in the tree.

Examples

Example 1

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

Output: [8,12,6,10,10,10]

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 details omitted.

Example 3

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

Output: [1,1]

Example details omitted.

Constraints

1 <= n <= 3 * 104
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
The given input represents a valid tree.

Solution Approach

Initial Calculation Using Depth-First Search

Start by calculating the distance of all nodes from a single node using DFS. This can help initialize the sum of distances for one node and act as a foundation for computing the sums for the remaining nodes.

Propagating the Results to Other Nodes

Once the sum of distances is computed for one node, use a second DFS pass to propagate the results to all other nodes. By utilizing the relationship between a parent and its children, you can adjust the sum of distances efficiently without recalculating from scratch.

Dynamic Programming for Optimization

To further optimize, use dynamic programming to store the intermediate results. This reduces redundant calculations, allowing the algorithm to complete in linear time relative to the number of nodes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(n) due to the two passes of DFS across all nodes. Space complexity is also O(n), as we store results for each node and perform recursive DFS calls.

What Interviewers Usually Probe

Candidate should demonstrate familiarity with tree traversal algorithms.
The candidate must efficiently propagate calculations from one node to others.
Look for a clear understanding of how dynamic programming can optimize the process.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the relationship between the sum of distances for a parent and its children, leading to inefficient recomputation.
Failing to use dynamic programming, resulting in redundant calculations and a time complexity that exceeds acceptable limits.
Not properly handling edge cases, such as when n = 1 or n = 2.

Follow-up variants

Modify the problem to calculate the sum of distances for a specific subset of nodes rather than all nodes.
Alter the tree structure by introducing different types of edges (e.g., weighted edges) and adjusting the solution approach.
Explore the problem using a breadth-first search (BFS) approach instead of DFS to see how the complexity and approach might change.

FAQ

What is the optimal time complexity for the Sum of Distances in Tree problem?

The optimal time complexity is O(n), where n is the number of nodes in the tree, achieved by using two passes of depth-first search.

How can dynamic programming help with this problem?

Dynamic programming helps by storing intermediate results, allowing for efficient propagation of distance sums without redundant calculations.

What’s the main challenge in solving the Sum of Distances in Tree problem?

The main challenge is efficiently computing the sum of distances for each node, which requires avoiding recalculating distances for every node pair.

Can breadth-first search (BFS) be used instead of depth-first search for this problem?

While BFS can be used, DFS is typically more efficient in this problem due to its natural recursive structure and ease of propagation for distance sums.

What should I focus on when approaching the Sum of Distances in Tree problem during an interview?

Focus on efficient tree traversal using DFS and dynamic programming to optimize the distance sum calculation for all nodes.

terminal

Solution

Solution 1: Tree DP (Re-rooting)

First, we run a DFS to calculate the size of each node's subtree, recorded in the array $size$, and compute the sum of distances from node $0$ to all other nodes, recorded in $ans[0]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class Solution:
    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
        def dfs1(i: int, fa: int, d: int):
            ans[0] += d
            size[i] = 1
            for j in g[i]:
                if j != fa:
                    dfs1(j, i, d + 1)
                    size[i] += size[j]

        def dfs2(i: int, fa: int, t: int):
            ans[i] = t
            for j in g[i]:
                if j != fa:
                    dfs2(j, i, t - size[j] + n - size[j])

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)

        ans = [0] * n
        size = [0] * n
        dfs1(0, -1, 0)
        dfs2(0, -1, ans[0])
        return ans

Continue Practicing

#787 cheapest flights within k stops #968 binary tree cameras #337 house robber iii