Hey guys,

I have this question.

Given a tree T = (V , F), find an algorithm which finds u in V, so in the graph T = (V \ {u} , F) the size of each connected component is |V| / 2 at most. What is the complexity?

I need to split this tree down the middle somehow, any idea?

Thanks a lot.

Assaf