310. Minimum Height Trees

A tree has n nodes labeled 0..n−1 and the given undirected edges. Choosing any node as the root gives a rooted tree with some height. Return all roots that give the minimum height, in any order.

The best roots are the center of the longest path. Peel off all leaves layer by layer, like an onion. The last one or two nodes standing are the centers.

1function findMinHeightTrees(n: number, edges: number[][]): number[] {
2  if (n <= 2) return Array.from({ length: n }, (_, i) => i);
3  const adj: Set<number>[] = Array.from({ length: n }, () => new Set());
4  for (const [a, b] of edges) { adj[a].add(b); adj[b].add(a); }
5  let leaves = adj.flatMap((s, i) => (s.size === 1 ? [i] : [])), remaining = n;
6  while (remaining > 2) {
7    remaining -= leaves.length;
8    const next: number[] = [];
9    for (const leaf of leaves) {
10      const [nb] = adj[leaf];
11      adj[nb].delete(leaf);
12      if (adj[nb].size === 1) next.push(nb);
13    }
14    leaves = next;
15  }
16  return leaves;
17}

remaining = 7

tree

degree

leaves

Initial leaves: [0,2,5,6].

1 / 0

Space: play/pause · ←/→: step