Minimum Height Trees

Problem

You are given a tree with n nodes labelled 0 to n - 1, described by a list of n - 1 undirected edges. Any node can be chosen as the root; rooting the tree at node r gives it a height equal to the number of edges on the longest downward path from r. Return the labels of every node that, when chosen as root, yields the minimum possible height. Return them in any order.

• There are at most 30,000 nodes.
• edges has exactly n - 1 entries and forms a single connected tree.

Examples

• n = 5, edges = [[2,0],[2,1],[2,3],[2,4]] → [2]. Rooting at the hub gives height 1; any leaf gives height 2.
• n = 6, edges = [[0,2],[0,3],[0,4],[0,1],[5,1]] → [0, 1]. Both have height 2; the tree's longest path has 4 nodes, so the two middle ones tie.
• n = 1, edges = [] → [0]. The only node.

Hints

1. Computing the height from every candidate root is n traversals. Which nodes are obviously bad roots?
2. If you delete every leaf at once, does the set of best roots change?
3. Repeatedly strip all current leaves (nodes of degree 1) in rounds; the last one or two nodes remaining are the answer. This is Kahn's algorithm applied to an undirected tree.