Sum Of Node Distances

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
3 upvotes
Asked in companies
DelhiveryBNY MellonMicrosoft

Problem statement

You have been given an array/list ‘EDGES’ of size (N - 1) x 2 representing the undirected connected tree with ‘N’ nodes from 0…’N’ - 1 and ‘N’ - 1 edges such that the i’th edge connects ‘EDGES[i][0]’ node with ‘EDGES[i][1]’ node.

You need to print an array/list ‘ANS’, where ANS[i] is the sum of the distances between node ‘i’ and all other nodes.

For example:

For ‘N’ = 6 and ‘EDGES’ = [ [0,1], [0, 2], [2, 3], [2, 4], [2, 5] ], see the below picture for reference:

img

1. For node 0:
   a. Distance from node 0 to node 1 is 1.
   b. Distance from node 0 to node 2 is 1.
   c. Distance from node 0 to node 3 is 2.
   d. Distance from node 0 to node 4 is 2.
   e. Distance from node 0 to node 5 is 2.
   So the sum of all the distances is 8.

2. For node 1:
   a. Distance from node 1 to node 0 is 1.
   b. Distance from node 1 to node 2 is 2.
   c. Distance from node 1 to node 3 is 3.
   d. Distance from node 1 to node 4 is 3.
   e. Distance from node 1 to node 5 is 3.
   So the sum of all the distances is 12.

3. For node 2:
   a. Distance from node 2 to node 0 is 1.
   b. Distance from node 2 to node 1 is 2.
   c. Distance from node 2 to node 3 is 1.
   d. Distance from node 2 to node 4 is 1.
   e. Distance from node 2 to node 5 is 1.
   So the sum of all the distances is 6.

4. For node 3:
   a. Distance from node 3 to node 0 is 2.
   b. Distance from node 3 to node 1 is 3.
   c. Distance from node 3 to node 2 is 1.
   d. Distance from node 3 to node 4 is 2.
   e. Distance from node 3 to node 5 is 2.
   So the sum of all the distances is 6.

5. For node 4:
   a. Distance from node 4 to node 0 is 2.
   b. Distance from node 4 to node 1 is 3.
   c. Distance from node 4 to node 2 is 1.
   d. Distance from node 4 to node 3 is 2.
   e. Distance from node 4 to node 5 is 2.
   So the sum of all the distances is 6.

6. For node 5:
   a. Distance from node 5 to node 0 is 2.
   b. Distance from node 5 to node 1 is 3.
   c. Distance from node 5 to node 2 is 1.
   d. Distance from node 5 to node 3 is 2.
   e. Distance from node 5 to node 4 is 2.
   So the sum of all the distances is 6.

So, ‘ANS’ for the above example will be [8, 12, 6, 10, 10, 10].
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.

The first line of each test case contains an integer ‘N’ representing the number of nodes in the tree.

The next ‘N’ - 1 lines of each test case contains two single space separated integers denoting ‘EDGES[i][0]’ and ‘EDGES[i][1]’.
Output Format : 
For each test case, print a single line containing space-separated integers denoting the sum of distances of each node from a node.

The output for each test case is printed in a separate line.
Note: 
You don't have to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 100
1 <= N <= 10 ^ 4
0 <= EDGE[i][0] and EDGE[i][1] < N

Time limit: 1 sec
Sample Input 1 :
2
2
0 1
3
0 1
0 2
Sample Output 1:
1 1
2 3 3

Explanation for Sample Output 1:

For the first test case :
See the picture below for the output reference:

img

1. For node 0:
   a. Distance from node 0 to node 1 is 1.
   So the sum of all the distances is 1.
2. For node 1:
   a. Distance from node 1 to node 0 is 1.
   So the sum of all the distances is 1.

For the second test case :
See the picture below for the output reference:

img

1. For node 0:
   a. Distance from node 0 to node 1 is 1.
   b. Distance from node 0 to node 2 is 1.
   So the sum of all the distances is 2.

2. For node 1:
   a. Distance from node 1 to node 0 is 1.
   b. Distance from node 1 to node 2 is 2.
   So the sum of all the distances is 3.

3. For node 2:
   a. Distance from node 2 to node 0 is 1.
   b. Distance from node 2 to node 1 is 2.
   So the sum of all the distances is 3.
Sample Input 2 :
2
4
1 0
1 2
2 3
1
Sample Output 2 :
6 4 4 6
0

Explanation for Sample Output 2:

For the first test case:
See the picture below for the output reference:

img

For the second test case :
There is only one node in the tree so the sum of distances from all the nodes will be 0.
Hint

Try finding the distance using DFS.

Approaches (1)
DFS

We can find the distance from a node from all other nodes in linear time. If we move our root from one node to its connected node, then one part of the node gets closer, and the other part gets further.

 

We try to find how many nodes are in both the parts, and then we can solve this problem. In one single traversal in the tree, we should get enough information for it and don't need to do it repeatedly.

 

As shown in the picture below, the answer for node ‘A’ subtree is 3 and answer for ‘B’ subtree is 6. Now if you observe carefully for the whole tree, the ‘ANS[A]’ = ‘ANS[A]’(subtree) + ‘ANS[B]’(subtree) + number of nodes in ‘B’ subtree. We use this observation to find our ‘ANS’ list/array in linear time.

 

 

 

 

Here is the complete algorithm:

  • Make the undirected graph ‘TREE’ using given ‘EDGES’.
  • Make an array/list ‘count’ initialize it with 1, an array/list ‘result’ initialized with 0.
  • Call our ‘DFS_UTIL1’ function and pass 0’th node and -1 as its parent. The ‘DFS_UTIL1’ function is explained below:
    • For each neighbor of the current node do the following:
      • Call ‘DFS_UTIL1’ function for all the neighbors of the current node.
      • After the call update ‘count[node]’ = ‘count[node]’ + ‘count[neighbour]’.
      • Update ‘result’ as ‘result[node]’ = ‘result[node]’ + ‘result[neighbour]’ + ‘count[neighbour]’.
  • Now Call ‘DFS_UTIL_2’ and pass 0 as root and -1 as the parent of the root. ‘DFS_UTIL_2’ function is explained below:
    • For each neighbour of the current node do the following:
      • Update ‘result[neighbour]’ = ‘res[node]’ + ‘count[neighbour]’ + ‘N’ - ‘count[neighbour]’.
      • Call ‘DFS_UTIL2’ function for all the neighbors of the current node.
  • Finally, return ‘result’.
Time Complexity

O(N), where ‘N’ is the number of nodes in the given tree.

 

Because we are traversing each node at most 2 times. Hence overall time complexity will be O(N).

Space Complexity

O(N), where ‘N’ is the number of nodes in the given tree.

 

In the worst case the size of the recursion stack will be ‘N’. Hence overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Sum Of Node Distances
Full screen
Console