DEV Community

Cover image for 834. Sum of Distances in Tree
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on • Edited on

834. Sum of Distances in Tree

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] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.

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

Example 1:

lc-sumdist1

  • 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:

lc-sumdist2

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

Example 3:

lc-sumdist3

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

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:

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:

  1. Tree Representation: Represent the tree using an adjacency list. This helps in efficient traversal using DFS.
  2. First DFS (dfs1):
    • Calculate the size of each subtree.
    • Compute the sum of distances from the root node to all other nodes.
  3. 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:

  1. Build the Graph: Convert the edge list into an adjacency list for efficient traversal.
  2. 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.
  3. 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]
?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  1. Graph Construction: array_fill initializes the adjacency list, ans, and size arrays.
  2. dfs1 Function: Calculates the total distance from the root and subtree sizes.
  3. 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:

Heroku

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay