Minimum Height Trees

Problem (restated)

Undirected tree with n nodes. Return all roots that minimize the height of the rooted tree (1 or 2 centroids).

Intuition

Repeatedly remove leaves (degree 1). Last remaining 1-2 nodes are the centers / MHT roots.

Approaches

export function findMinHeightTrees(n: number, edges: number[][]): number[] {
  if (n === 1) return [0];
  const g: number[][] = Array.from({ length: n }, () => []);
  const deg = Array(n).fill(0);
  for (const e of edges) {
    g[e[0]!]!.push(e[1]!);
    g[e[1]!]!.push(e[0]!);
    deg[e[0]!]!++;
    deg[e[1]!]!++;
  }
  let q: number[] = [];
  for (let i = 0; i < n; i++) if (deg[i] === 1) q.push(i);
  let remain = n;
  while (remain > 2) {
    const next: number[] = [];
    remain -= q.length;
    for (const u of q) {
      for (const v of g[u]!) {
        if (--deg[v]! === 1) next.push(v);
      }
    }
    q = next;
  }
  return q;
}

export function findMinHeightTrees(n: number, edges: number[][]): number[] {
  if (n === 1) return [0];
  const g: number[][] = Array.from({ length: n }, () => []);
  const deg = Array(n).fill(0);
  for (const e of edges) {
    g[e[0]!]!.push(e[1]!);
    g[e[1]!]!.push(e[0]!);
    deg[e[0]!]!++;
    deg[e[1]!]!++;
  }
  let q: number[] = [];
  for (let i = 0; i < n; i++) if (deg[i] === 1) q.push(i);
  let remain = n;
  while (remain > 2) {
    const next: number[] = [];
    remain -= q.length;
    for (const u of q) {
      for (const v of g[u]!) {
        if (--deg[v]! === 1) next.push(v);
      }
    }
    q = next;
  }
  return q;
}

Template connection

Layered leaf removal (topo-like on trees).

Reflection

• Peel degree-1 leaves. The last round leaves one or two nodes, and those are the centers. When n <= 2, every node is an answer.
• The input is a tree, so there is no cycle. A round cuts only the leaves you queued. A node that becomes a leaf during the round waits.
• The middle of a chain is one or two nodes. A star keeps the center.