834. Sum of Distances in Tree

Difficulty: Hard

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

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⁴
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.

Solution:

We use a combination of Depth-First Search (DFS) and dynamic programming techniques. The goal is to efficiently compute the sum of distances for each node in a tree with n nodes and n-1 edges.

Approach:

Tree Representation: Represent the tree using an adjacency list. This helps in efficient traversal using DFS.
First DFS (dfs1):
- Calculate the size of each subtree.
- Compute the sum of distances from the root node to all other nodes.
Second DFS (dfs2):
- Use the results from the first DFS to compute the sum of distances for all nodes.
- Adjust the results based on the parent's result.

Detailed Steps:

Build the Graph: Convert the edge list into an adjacency list for efficient traversal.
First DFS:
- Start from the root node (typically node 0).
- Compute the size of each subtree and the total distance from the root node to all other nodes.
Second DFS:
- Compute the distance sums for all nodes using the information from the first DFS.
- Adjust the distance sum based on the parent node’s result.

Let's implement this solution in PHP: 834. Sum of Distances in Tree

<?php
/**
 * @param Integer $n
 * @param Integer[][] $edges
 * @return Integer[]
 */
function sumOfDistancesInTree($n, $edges) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$n1 = 6;
$edges1 = [[0,1],[0,2],[2,3],[2,4],[2,5]];
print_r(sumOfDistancesInTree($n1, $edges1));  // Output: [8,12,6,10,10,10]

$n2 = 1;
$edges2 = [];
print_r(sumOfDistancesInTree($n2, $edges2));  // Output: [0]

$n3 = 2;
$edges3 = [[1,0]];
print_r(sumOfDistancesInTree($n3, $edges3));  // Output: [1,1]
?>

Explanation:

Graph Construction: array_fill initializes the adjacency list, ans, and size arrays.
dfs1 Function: Calculates the total distance from the root and subtree sizes.
dfs2 Function: Adjusts distances for all nodes based on the result from dfs1.

This approach efficiently computes the required distances using two DFS traversals, achieving a time complexity of O(n), which is suitable for large trees as specified in the problem constraints.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub