We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum of Distances in Tree

Difficulty: Hard

Problem Description

Given an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges, 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.

Key Insights

  • The problem can be solved using Depth-First Search (DFS) to calculate distances efficiently.
  • By calculating the distance sum for a root node, we can derive the distance sums for its children using a relationship based on the number of nodes in each subtree.
  • The overall complexity can be handled within O(n) time, which is efficient for the input constraints.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use a two-pass DFS approach:

  1. In the first DFS pass, we compute the total distance from the root node (chosen arbitrarily, say node 0) to all other nodes and also count the number of nodes in each subtree.
  2. In the second DFS pass, we calculate the distance sum for each node based on its parent's distance sum and the sizes of the subtrees.

The key data structures used are:

  • An adjacency list to represent the tree.
  • Arrays to store the distance sums and subtree sizes.

Code Solutions

from collections import defaultdict

def sumOfDistancesInTree(n, edges):
    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)

    answer = [0] * n
    count = [1] * n  # count of nodes in the subtree
    visited = [False] * n

    def dfs1(node, parent):
        for neighbor in graph[node]:
            if neighbor == parent:
                continue
            dfs1(neighbor, node)
            count[node] += count[neighbor]
            answer[node] += answer[neighbor] + count[neighbor]

    def dfs2(node, parent):
        for neighbor in graph[node]:
            if neighbor == parent:
                continue
            answer[neighbor] = answer[node] - count[neighbor] + (n - count[neighbor])
            dfs2(neighbor, node)

    dfs1(0, -1)  # First DFS to calculate initial distances
    dfs2(0, -1)  # Second DFS to update distances for each node

    return answer
← Back to All Questions