Center node in a tree (in a minimum sum of distances sense)

Question

My problem is the following:

Given a tree (V, E), find the center node v such that sum{w in V}[dist(v,w)] is minimum, where dist(v,w) is the number of edges in shortest path from v to w. The algorithm should run in O(n) time (n being the number of nodes in a tree).

The questions here and here also ask for the center node but define it differently.

I haven't rigorously gone through the steps but I actually think that the solution to my problem should be similar to the solution of this problem.

However, I decided that I should share my problem with the community as it took me a while to navigate to the link, which however does not answer the question directly.

Answer 1

I came up with this solution:

1) Choose an arbitrary node as a root r, form a tree. For each subtree in this tree, calculate number of nodes in a subtree (the leaves are single-node-trees).

As an example for this tree

          1
        / | \
       2  3  4 
      / \     \
     5   6     7
        / \
       8   9      

the result would be

          9
        / | \
       5  1  2 
      / \     \
     1   3     1
        / \
       1   1    

2) Calculate the sum of distances for this chosen root. For the example, if you choose vertex 1 as a root, the sum of distances is 0 + 1 + 1 + 1 + 2 + 2 + 2 + 3 + 3 = 15

3) Traverse the tree in a depth-first-search manner. For example, starting from vertex 1, we traverse to vertex 4. We observe that for 7 nodes (1,2,3,5,6,8,9), we are getting further by 1 (add 7=9-2 to the score), for other 2 (4,7), we are getting closer by 1 (subtract 2). This gives the sum-of-distances equal to 15+(9-2)-2 = 20.

Suppose we traverse from 4 to 7 next. Now we get the sum of distances equal to 20+(9-1)-1 = 27 (getting further from 8 vertices, and getting closer to 1 vertex).

As another example if we traverse from 1 to 2, we get a sum of distances equal to 15+(9-5)-5 = 14. Vertex 2 is actually the solution for this example.

This would be my algorithm.