Efficient Algorithm to compute radius of tree

Yes, it can be done in $O(n)$ time.

Rooted trees

First let me describe how to do it for a rooted tree. We'll compute several quantities for each node $v$ in the tree:

• Let $p(v)$ denote $v$'s parent.

• Let $h(v)$ denote the height of $v$ (i.e., the distance from $v$ to its deepest descendant). You can compute $h(v)$ for all nodes $v$ in $O(n)$ time via a simple recursive traversal.

• Let $f(v)$ denote the length of the longest simple path that starts $v \to p(v) \to w \to \cdots$ such that $w$ is a sibling of $v$, i.e., $p(v)=p(w)$ and $v \ne w$. In other words, it's the length of the longest path that starts from $v$ by going up once and then immediately going down. Note that

  $$f(v) = \max \{2+h(w) : p(w)=p(v), w \ne v\}.$$

  Suppose we've computed $h(v)$ for all nodes $v$. Also, suppose that for each node we keep track of its two children with the two largest $h(\cdot)$ values. Then, we can compute $f(v)$ for each node $v$ easily.

• Let $g(v)$ denote the length of the longest simple path that starts $v \to p(v) \to \cdots$. In other words, it's the length of the longest path that starts by going up from $v$ (possibly several times). Note that $g(v) = \max \{ f(p^i(v))+i : i \ge 0\}$ and moreover

  $$g(v) = \max(f(v), g(p(v))+1).$$

  Therefore, if you've computed $f(v)$ for all nodes $v$, you can easily compute $g(v)$ for all nodes via a simple recursive traversal.

• Let $e(v)$ denote the eccentricity of node $v$, i.e., $e(v) = \max\{d(v,w) : w \in V\}$. The eccentricity of a node $v$ is given by $e(v) = \max(h(v),g(v))$.

This gives us a way to label all the nodes with their eccentricity, in $O(n)$ time. Then we simply find the node whose eccentricity is the smallest. The algorithm runs in $O(n)$ time in all.

Unrooted trees

If we have an unrooted tree (as in the question), we can first turn it into a rooted tree (do a DFS; then the DFS tree will be a rooted version of the tree), then apply the previous algorithm.