centre node in a tree

Question

Given a tree, how to find the centre node in the tree so that the distance from the central node to other nodes is minimum(assuming each edge has unit weight)? I am trying to use DFS but is it possible to do it in linear time?

Answer 1

Keep removing leaf nodes from your tree until you are left with a single node (if left with two nodes, remove any one of them). That node minimizes the maximum distance from it to every other node.

Example:

   *                 *              
  / \                 \
 *   *                 *              *
      \                 \              \
       *      =>         *     =>       *    =>   *
        \                 \                     
         *                 *
          \
           *

To implement this in linear time, insert all initial leaf nodes in a FIFO queue. For each node, also store the number of its children. When removing an element from your queue, decrease its parent's number of children. If this number becomes zero, insert the parent into the queue.

Answer 2

Here is another approach that also runs in O(V).

Select any vertex v1 on your tree. Run BFS from this vertex. The last vertex (v2) you will proceed will be the furthest vertex from v1. Now run another BFS, this time from vertex v2 and get the last vertex v3.

The path from v2 to v3 is the diameter of the tree and your center lies somewhere on it. More precisely it lies in the middle of it. If the path has 2n + 1 points, there will be only 1 center (in the position n + 1). If the path has 2n points, there will be two centers at the positions n and n + 1.

You only use 2 BFS calls which runs in 2 * O(V) time.