Removing the Node That Splits It Best
Remove exactly ONE node from a tree, along with every edge touching it. What remains is a collection of pieces. Print the smallest possible size of the LARGEST piece, over all choices of node.
4 nodes, edges 1-2 1-3 3-4 -> 2 removing node 1 leaves {2} and {3,4}
5 nodes in a star -> 1 removing the centre leaves four single nodes
## What the pieces are
Root at node 1. Removing node u leaves one piece for each child of u, namely that child's
subtree, and, when u is not the root, ONE more piece: everything that was above u.
That last piece is the part people forget, and it has a short formula:
size of the piece above u = n - size[u]
because the tree has n nodes, size[u] of them are in u's subtree, and removing u leaves
the rest connected through the parent.
## The scan
One children-first sweep gives every size[u]. Then, for each u:
largest(u) = max( n - size[u], max over children c of size[c] )
and the answer is the smallest largest(u).
For the root, n - size[1] is 0, which is harmless inside a maximum, so the formula needs no
special case.
## What this node is
The node achieving the minimum is called a CENTROID, and it always satisfies
largest <= n / 2. That bound is worth knowing but it is not needed here: the scan finds the
minimum directly, whatever it turns out to be.
A tree can have two centroids, on a path of an even number of nodes for instance. The problem asks for the SIZE, not the node, so the tie needs no rule.
## Boundaries
A single node removed leaves nothing at all, so the answer is 0. A solution that takes a maximum over an empty list must start that maximum at 0 rather than at a large sentinel.
On a path of eight the answer is 4: removing either middle node leaves pieces of 3 and 4.
## Cost
Time O(n). Space O(n).