Media.net interview question.
Q.

You are given a rooted binary tree with weights on edges. The distance between two nodes in this tree is the sum of the edge weights on the path between the two nodes. SUM[u] is the sum of the distances between u and all the other nodes in the tree.

task1 : Calculate SUM[root]
task2 : Calculate the array SUM for all nodes 1 to N.

Example :

                    1(root)
            /(50)             \(10)
           2                   3
     (10)/   \(10)       (30)/   \(20)
       6      7             4     5
          (3)/ \(4)
            8   9

Sum[1] = 377
Sum[2] = 327
Sum[6] = 277
....

Expected time complexity = O(N).
N = Number of node in given tree.