Minimum Height Trees

1. Define the problem

You are given an undirected tree of n nodes labeled 0 to n - 1 and its n - 1 edges. Choosing any node as the root gives a rooted tree with some height. Return every node that, chosen as root, produces the minimum possible height . There will be at most two such roots — they're the tree's centroids. Find them by repeatedly trimming the leaves layer by layer until at most two nodes remain.

Constraints

1 ≤ n ≤ 2 × 10⁴
edges.length == n - 1
The given input is guaranteed to be a tree

Example

Inputn = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]

Output[3, 4]

Explanation Rooting the tree at 3 or at 4 both produce the shortest possible tree height.

2. Know the words first

In plain terms

Leaf: A node with only one connection — a dead end at the current outer edge of the tree.
Trimming the leaves: Removing every current leaf at once — the same in-degree-zero peeling as topological sort, using a node's remaining connection count instead of a directed in-degree.

3. Visualize the solution

Peel leaves layer by layer until 1 or 2 centers remain

Statusinit

Connections: 0,1,2,5 have 1 each — they are the first leaves. 3 has 4, 4 has 2.

What happens in this step

degree[0] = 1, degree[1] = 1, degree[2] = 1, degree[5] = 1
degree[3] = 4, degree[4] = 2

leaves = [0, 1, 2, 5]

Every node with exactly one connection is a leaf. Nodes 0, 1, 2, and 5 each connect only to node 3 or node 4, so they form the first layer to trim.

Step 1 of 3

Steps to visualize

Build the tree as an adjacency list and find every node with exactly one connection — a leaf.
Remove every current leaf at once, decrementing the connection count of its one neighbor.
Any node whose connection count just dropped to one becomes a leaf for the next round.
Repeat until at most two nodes remain — those are the roots of a minimum height tree.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Peel leaves layer by layer until 1 or 2 centers remain

Statusinit

Connections: 0,1,2,5 have 1 each — they are the first leaves. 3 has 4, 4 has 2.

What happens in this step

degree[0] = 1, degree[1] = 1, degree[2] = 1, degree[5] = 1
degree[3] = 4, degree[4] = 2

leaves = [0, 1, 2, 5]

Every node with exactly one connection is a leaf. Nodes 0, 1, 2, and 5 each connect only to node 3 or node 4, so they form the first layer to trim.

Step 1 of 3

5. Solution

Solution

solution.tsTypeScript

function findMinHeightTrees(n, edges) {
  if (n === 1) {
    return [0];
  }

  const graph = Array.from({ length: n }, () => new Set());
  for (const [a, b] of edges) {
    graph[a].add(b);
    graph[b].add(a);
  }

  let leaves = [];
  for (let i = 0; i < n; i++) {
    if (graph[i].size === 1) {
      leaves.push(i);
    }
  }

  let remaining = n;

  while (remaining > 2) {
    remaining -= leaves.length;
    const nextLeaves = [];

    for (const leaf of leaves) {
      for (const neighbor of graph[leaf]) {
        graph[neighbor].delete(leaf);
        if (graph[neighbor].size === 1) {
          nextLeaves.push(neighbor);
        }
      }
      graph[leaf].clear();
    }

    leaves = nextLeaves;
  }

  return leaves.sort((a, b) => a - b);
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`n = 4, edges = [[1,0],[1,2],[1,3]]`	`[1]`	example from the docstring, a star centered on one node
`n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]`	`[3, 4]`	a tree with two equally central roots
`n = 1, edges = []`	`[0]`	smallest valid input, a single node with no edges
`n = 2, edges = [[0,1]]`	`[0, 1]`	exactly two nodes, both are centroids
`n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]`	`[2]`	a straight path with an odd number of nodes, one true center
`n = 4, edges = [[0,1],[1,2],[2,3]]`	`[1, 2]`	a straight path with an even number of nodes, two centers
`n = 3, edges = [[0,1],[1,2]]`	`[1]`	shortest odd path, three nodes
`n = 7, edges = [[0,1],[0,2],[0,3],[0,4],[0,5],[0,6]]`	`[0]`	a bigger star, confirming the hub is always the sole centroid

Minimum Height Trees