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:

1. Create an adjacency list that represents the tree from the given edges.
2. Initialize two arrays:
3. subtree_size: An array that stores the size of the subtree rooted at each node.
4. distance: An array that stores the distance of each node from the root.
5. Initialize the distance array with 0 for the root node.
6. Calculate the subtree_size and distance for all nodes using a depth-first search (DFS) traversal:
   a. Start the DFS from the root node.
   b. For each child of a node u, add 1 to subtree_size[u] and calculate distance[v] = distance[u] + 1.
   c. Recursively traverse all the children.
   d. After traversing all the children, add subtree_size[v] to subtree_size[u].
7. Initialize another array ans with 0.
8. 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 node u, calculate ans[v] = ans[u] + (n - subtree_size[v]) - subtree_size[v].
   c. Recursively traverse all the children.
9. 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;

}

}