Divide-And-Conquer Algorithm for Trees

Question

I am trying to write a divide & conquer algorithm for trees. For the divide step I need an algorithm that partitions a given undirected Graph G=(V,E) with n nodes and m edges into sub-trees by removing a node. All subgraphs should have the property that they don't contain more than n/2 nodes (the tree should be split as equal as possible). First I tried to recursively remove all leaves from the tree to find the last remaining node, then I tried to find the longest path in G and remove the middle node of it. The given graph below shows that both approaches don't work:

Is there some working algorithm that does what I want (returns the node H in the above case).

Answer 1

I think you could do it with an algorithm like this:

Start in the root (if the tree isn't rooted, pick any node).
In each step, try to descend into the child node that has the largest subtree (the number of nodes “below” it is the biggest).
If doing that would make the number of nodes “above” bigger than n/2, stop, otherwise continue with that child.

This algorithm should be O(log n) if the tree is reasonably balanced and we have sizes of subtrees precomputed for each node. If one of those conditions doesn't apply, it would be O(n).