Minimum Height Trees

Peel the tree from the outside

The roots with minimum height are the center or centers of a tree. Put every degree-one node in a queue, then remove the current layer of leaves simultaneously. Decrement each neighbor's degree and enqueue it when its degree becomes one. Continue until at most two nodes remain; those remaining nodes are the centers and are the required roots. This is analogous to trimming outer layers until the tree's radius is reached.

Why the centers remain

A leaf cannot be an optimal root when more than one node exists: moving one edge inward reduces its farthest distance. Removing all leaves preserves the center of the remaining tree, so repeating the argument leaves only the one center of an even-diameter tree or two adjacent centers of an odd-diameter tree. Handle n=1 explicitly, returning [0] even though it has degree zero. Each edge and node is processed a constant number of times, giving O(n) time and O(n) space. Test a path, a star, and a tree with two centers.