Finding the cut vertice of a tree with n vertices that returns connected components with a minimal number of vertices?

Question

i need to find an algorithm in O(n) time for my title question for a given tree G = (V,E) with n vertices. It should return the vertice n which after deleting from the tree results in a number of connecting components where the maximum number of vertices in a connected component is minimal among all possible cut vertices. My solution so far is:

1. s = starting node
2. cut_node = s //maybe initialize later in loop
3. maxNumComponent = []

if |V| == 0 || |V| == 1
   return null
if |V| == 2 
   return any node
for each v in V with degree[v] > 1 do //maybe do a while loop and mark visited node?
      deleteFromTree(v)
      currentMax = traverse resulting components & return max. number of vertices of all components
      maxNumComponent.add(currentMax)
      if currentMax is min of maxNumComponent
         cut_node=v
      addToTree(v)
return v

I would be happy for any help to optimize this approach or if there is an easier or simpler solution. Cheers

Answer 1

You could try rooting the tree at any vertex (it doesn't matter), and compute on each node the size of its subtree. This can be done in a single $O(n)$ pass.

Then, using this information, given a node, it should be possible to compute the value you're searching (the $\max$ of the sizes of the remaining components) without new traversals of the tree : for components below in the rooted tree, you have already computed those, and for the (unique) component that includes the root, it has all $n$ vertices except the ones in the subtree, so you know its size.

That whole computation has an (amortized) cost of $O(n)$.