Solution For Sum Of Distances In Tree
The Sum of Distances in Tree problem on LeetCode asks you to find the sum of distances between all pairs of nodes in a tree. The input is an array of edges that represent the tree. The output is an array of integers that represent the sum of distances for each node in the tree.
To solve this problem, we can use two traversals of the tree: one to calculate the subtree size and the distance from the root for each node, and another to calculate the sum of distances for each node.
Algorithm:
- Create an adjacency list that represents the tree from the given edges.
- Initialize two arrays:
subtree_size
: An array that stores the size of the subtree rooted at each node.distance
: An array that stores the distance of each node from the root.- Initialize the
distance
array with0
for the root node. - Calculate the
subtree_size
anddistance
for all nodes using a depth-first search (DFS) traversal:
a. Start the DFS from the root node.
b. For each child of a nodeu
, add 1 tosubtree_size[u]
and calculatedistance[v] = distance[u] + 1
.
c. Recursively traverse all the children.
d. After traversing all the children, addsubtree_size[v]
tosubtree_size[u]
. - Initialize another array
ans
with0
. - Traverse the tree again using DFS to calculate the
ans
array:
a. Start the DFS from the root node.
b. For each child of a nodeu
, calculateans[v] = ans[u] + (n - subtree_size[v]) - subtree_size[v]
.
c. Recursively traverse all the children. - Return the
ans
array.
The time complexity of this algorithm is O(N), where N is the number of nodes in the tree. This is because we traverse the tree twice using a DFS traversal, and at each node, we perform constant time operations.
Here is the implementation of the solution in Python:
“`
class Solution:
def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
# Step 1
adj = [[] for _ in range(N)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
# Step 2
subtree_size = [1] * N
distance = [0] * N
# Step 3
def dfs1(u, parent):
for v in adj[u]:
if v != parent:
distance[v] = distance[u] + 1
dfs1(v, u)
subtree_size[u] += subtree_size[v]
dfs1(0, -1)
# Step 4
ans = [0] * N
# Step 6
def dfs2(u, parent):
for v in adj[u]:
if v != parent:
ans[v] = ans[u] + (N - subtree_size[v]) - subtree_size[v]
dfs2(v, u)
dfs2(0, -1)
# Step 7
ans[0] = sum(distance)
for i in range(1, N):
ans[i] += ans[0] - 2 * distance[i]
return ans
“`
In this implementation, we used a recursive DFS traversal instead of an iterative DFS traversal for simplicity.
Step by Step Implementation For Sum Of Distances In Tree
class Solution { public int[] sumOfDistancesInTree(int N, int[][] edges) { // create an adjacency list List> adjList = new ArrayList<>(); for (int i = 0; i < N; i++) { adjList.add(new ArrayList<>()); } // add edges to the adjacency list for (int[] edge : edges) { int u = edge[0]; int v = edge[1]; adjList.get(u).add(v); adjList.get(v).add(u); } // array to store the sum of distances for each node int[] sum = new int[N]; // array to store the number of nodes reachable from each node int[] count = new int[N]; // boolean array to keep track of which nodes have been visited boolean[] visited = new boolean[N]; // do a dfs from each node to get the sum of distances and number of nodes reachable for (int i = 0; i < N; i++) { sum[i] = dfs(i, adjList, visited, sum, count); } return sum; } // dfs helper function private int dfs(int node, List
> adjList, boolean[] visited, int[] sum, int[] count) { visited[node] = true; int currSum = 0; int currCount = 1; for (int neighbor : adjList.get(node)) { if (!visited[neighbor]) { currSum += dfs(neighbor, adjList, visited, sum, count); currCount += count[neighbor]; } } sum[node] = currSum + (visited.length - 1 - currCount); count[node] = currCount; return sum[node]; } }
def sumOfDistancesInTree(N, edges): # Initialize an array of N zeros to store the sum of distances of each node to all other nodes sums = [0] * N # Initialize an array of N zeros to store the number of nodes reachable from each node counts = [0] * N # Perform a depth-first search starting from node 0 def dfs(node, parent): # Iterate over all nodes reachable from the current node for child in edges[node]: # If the child is the parent, skip it if child == parent: continue # Recursively visit the child node dfs(child, node) # Add the child's sum of distances to the current node's sum sums[node] += sums[child] # Add the child's number of nodes reachable to the current node's number counts[node] += counts[child] # Add the edge distance from the current node to the child node to the current node's sum sums[node] += 1 # Increment the number of nodes reachable by the current node by the number of nodes reachable by the child node counts[node] += 1 # Perform a depth-first search from node N-1 dfs(N-1, None) # Return the sum of distances of node 0 to all other nodes return sums[0]
var sumOfDistancesInTree = function(N, edges) { // create an array of N elements, each initialized to 0 let distances = new Array(N).fill(0); // create an array of N elements, each initialized to an empty array let children = new Array(N).fill().map(() => []); // iterate through each edge in the edges array for (let [u, v] of edges) { // add v to the list of children of u children[u].push(v); // add u to the list of children of v children[v].push(u); } // create a helper function to compute the sum of distances from node to all its children let dfs = function(node, parent) { // iterate through each child of node for (let child of children[node]) { // if child is not the parent if (child !== parent) { // recursively call dfs on child, passing in node as the parent dfs(child, node); // add child's distance to node's distance distances[node] += distances[child]; } } } // call dfs on node 0, with no parent (-1) dfs(0, -1); // create a helper function to compute the sum of distances from node to all its parents let dfs2 = function(node, parent) { // iterate through each child of node for (let child of children[node]) { // if child is not the parent if (child !== parent) { // add node's distance to child's distance distances[child] += distances[node]; // recursively call dfs2 on child, passing in node as the parent dfs2(child, node); } } } // call dfs2 on node 0, with no parent (-1) dfs2(0, -1); // return the distances array return distances; };
There are multiple ways to solve this problem. One approach is to do a breadth first search starting from each node. For each node, we can keep track of the number of nodes at each level. Then, we can iterate through all nodes at each level and update the sum of distances accordingly. Another approach is to do a depth first search. For each node, we can compute the sum of distances from that node to all other nodes in the tree. This can be done by keeping track of the number of nodes at each level and updating the sum accordingly.
The code for this problem is as follows: public class Solution { public int[] SumOfDistancesInTree(int N, int[][] edges) { int[] result = new int[N]; for (int i = 0; i < N; i++) { result[i] = CalculateSumOfDistances(i, edges, new bool[N]); } return result; } private int CalculateSumOfDistances(int current, int[][] edges, bool[] visited) { int sum = 0; visited[current] = true; foreach (var edge in edges) { if (edge[0] == current && !visited[edge[1]]) { sum += edge[2] + CalculateSumOfDistances(edge[1], edges, visited); } else if (edge[1] == current && !visited[edge[0]]) { sum += edge[2] + CalculateSumOfDistances(edge[0], edges, visited); } } return sum; } }