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:

Billboard image

Monitor more than uptime.

With Checkly, you can use Playwright tests and Javascript to monitor end-to-end scenarios in your NextJS, Astro, Remix, or other application.

Get started now!

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay