Minimum Height Trees
Find every root that gives a tree the smallest possible height by trimming its leaves layer by layer until the one or two centres are left.
Problem Understanding
Minimum Height Trees (LeetCode 310): you are given a tree of n nodes labelled 0 to n - 1 as a list of n - 1 undirected edges. Choosing any node as the root gives a rooted tree with some height, the number of edges on its longest root-to-leaf path. Return every root that gives the minimum height, in any order.
Examples: n = 4, edges = [[1,0],[1,2],[1,3]] → [1]; n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] → [3, 4].
The Intuition: Peel the Tree Like an Onion
The best root is the one in the middle, and a leaf is never in the middle unless the tree has at most two nodes.
- Find the leaves: nodes with one neighbour.
- Remove them all at once. Their neighbours lose a connection; any left with one neighbour are the next layer's leaves.
- Stop at 2 or fewer nodes. Those are the centres.
Peeling nodes that have run out of connections is Topological Sort (Kahn's algorithm) applied to an undirected tree; Course Schedule peels the same way on a directed graph.
Interactive Walkthrough
NUMBER = NEIGHBOURS LEFT
BUILD NEIGHBOURS
remaining
6
leaves
0
centres
:
Build the neighbour sets of 6 nodes from 5 edges
Next
Nodes with one neighbour are the leaves: 0, 1, 2, 5. They can never be the best root
edges
n
The number above each node is how many neighbours it still has. Trimmed nodes fade and show the layer they left in. Compare Odd path and Even path: an odd number of nodes on the longest path leaves one centre, an even number leaves two.
Dry Run Table
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]].
| Step | Action | Neighbours left | Remaining |
|---|---|---|---|
| Leaves | nodes with one neighbour: 0, 1, 2, 5 | 3 has 4, 4 has 2 | 6 |
| Trim 0, 1, 2 | 3 loses three neighbours; it now has 1, so it joins the next layer | 3 has 1 | 2 |
| Trim 5 | 4 loses a neighbour; it now has 1, so it joins the next layer | 4 has 1 | 2 |
| Stop | 2 nodes remain | 2 |
Answer: [3, 4]. Rooted at 3 or at 4, the tree has height 2; any other root gives height 3.
The Solution Template
Neighbour sets and a layer-by-layer queue of leaves. The C version keeps a degree and the XOR of each node's neighbours instead of sets: once a node is a leaf, that XOR is its last neighbour.
Minimum Height Trees Code
1var findMinHeightTrees = function(n, edges) {2 if (n === 1) {3 return [0];4 }5 const neighbors = Array.from({ length: n }, () => new Set());6 for (const [a, b] of edges) {7 neighbors[a].add(b);8 neighbors[b].add(a);9 }10 let leaves = [];11 for (let v = 0; v < n; v++) {12 if (neighbors[v].size === 1) {13 leaves.push(v);14 }15 }16 let remaining = n;17 while (remaining > 2) {18 remaining -= leaves.length;19 const nextLeaves = [];20 for (const leaf of leaves) {21 const [other] = neighbors[leaf];22 neighbors[other].delete(leaf);23 if (neighbors[other].size === 1) {24 nextLeaves.push(other);25 }26 }27 leaves = nextLeaves;28 }29 return leaves;30};
Edge Cases & Common Mistakes
- n = 1: no edges and no leaves; return [0] before anything else.
- n = 2: both nodes are leaves and both are centres; the loop never runs.
- Stopping at one node: the answer can be two nodes, so stop when 2 or fewer remain, not 1.
- Removing leaves one at a time: trim a whole layer before looking at the new leaves, or nodes from different layers get mixed and the wrong centre can be left.
- Running BFS from every root: correct but O(n^2).
Summary
Collect the leaves, remove them a layer at a time, and add any node left with one neighbour to the next layer. When 2 or fewer nodes remain, they are the minimum height roots. O(n) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet