Please suggest some algorithm to find the node in a tree whose distance to its farthest node is minimum among all the nodes

Question

Please suggest some algorithm to find the node in a tree whose distance to its farthest node is minimum among all the nodes.

Its is not a graph and it is not weighted.

Answer 1

Choose an arbitrary node v in the tree T. Run BFS making v as the root of T. BFS outputs the distances from v to all the other nodes of T.

Now choose a node u that is farthest from v. Run again BFS making u as the root. On the new distance output, find a node w that is farthest from u.

Consider the path between u and w. This is the longest path in the tree T. The node in the midle of the path is the center of the tree T.

Note that there may exist two centers in a tree. If so, they are neighbours.

Performance: O(n), where n is the number of nodes of T.

Proof

Claim: a leaf (u) that is furthest from some node v lies on the longest path.

If we prove it, then the algorithm is correct, since it first finds u, and, since it's one end of the longest path, uses DFS to find this path itself.

Proof of the claim: Let's use retucto ad absurdum. Assume u---r is the longest path in the tree; and for some node v neither v---u, nor v---r is the longest path from v. Instead, the longest path is v---k. We have two cases:

a) u---r and v--k have a common node o. Then v--o--u and v--o--r are shorter than u---o---k. Then o---r is shorter than o---k. Then u---o---r is not the longest path in graph, because u---o---k is longer. It contradicts our assumption.

b) u---r and v--k don't have common nodes. But since the graph is connected, there are nodes o1 and o2 on each of these paths, such that the path between them o1--o2 doesn't contain any other nodes on these two paths. The contradiction to the assumption is the same as in point a), but with o1--o2 instead of mere o (in fact, point a is just a special case of b, where o1=o2).

This proves the claim and hence the correctness of the algorithm.

(this is proof written by Pavel Shved, and the original author might have a shorter one).

Answer 2

Remove leaves. If more than 2 nodes left, repeat. The node (or 2 nodes) left will be the node you are looking for.

Why this works:

The node(s) are in the middle of the longest path P in the tree. Their max distance to any node is at most half of the length of the path (otherwise it would not be the longest one). Any other node on P will obviously have greater distance to the further end of P than the found node(s). Any node n not on P will have its furthest node at least (distance from n to the closest node on P, say c) + (distance from c to the further end of P), so again more than the node(s) found by the algorithm.