Given a tree, find a vertex which maximizes the minimum distance to any leaf
To find a vertex of maximum distance from any leaf, you can perform a breadth-first search starting from many starting points, i.e. the leaves. Because a BFS visits each node by the shortest possible path from the source(s) of the search, we can easily attribute to each node the distance to the nearest leaf.


Insert into a queue a collection of pairs $(\ell,0)$ for $\ell$ ranging over all leaves, and record $\textrm{max} = 0$.
Repeat the following until the queue is empty:


Pop a pair $(v,d)$ off the queue. If $d = \textrm{max}$, insert $v$ in a collection of maximum-distance elements.
If there are nodes adjacent to $v$ which haven't been visited, push a pair $(w,d+1)$ into the queue for each such neighbour $w$, marking them as having been visited. If there are any such $w$ at all, empty the collection of maximum-distance elements (if it is non-empty), and set $\textrm{max} = d+1$.



The result is a collection of nodes which are all at distance at least $\textrm{max}$ from any leaf. 

Let $n = |V|$ (note that $m = |E| = n-1$). Assuming that we can populate the queue with the leaves of the tree in time $O(n)$ by examining all nodes of the graph, and that the vertices have adjacency lists of their neighbours, we "traverse" each edge twice to consider the neighbours of each vertex; then this algorithm takes $O(n+m) = O(n)$ time. It also works for non-trees, taking again $O(n+m)$ time.