A tree is an undirected graph in which any two vertices are connected by exactly one path. Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [aᵢ, bᵢ] indicates an undirected edge between nodes aᵢ and bᵢ, you can choose any node of the tree as the root.
When you pick a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).
Return a list of all the root labels of the minimum height trees. You can return the answer in any order.
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
How your function is called
findMinHeightTrees(n, edges) -> list of root labels
The input is fed as: the number of nodes n, then the number of edges m, then m lines each holding one edge a b.
remaining <= 2 captures both cases.[0].Input: n = 4, edges = [[1,0],[1,2],[1,3]] Output: [1] Rooting the tree at node 1 gives height 1 — the minimum. Every other root gives height 2.
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] Output: [3,4] Both node 3 and node 4 give a tree of height 2 — the minimum. They are the two centers of the tree.
Input: n = 1, edges = [] Output: [0] A single node is trivially its own minimum height tree.
- 1 <= n <= 2 * 10^4 - edges.length == n - 1 - 0 <= a_i, b_i < n - a_i != b_i - The given input is guaranteed to be a tree (connected, acyclic).
Minimum Height Trees is a rite-of-passage graph problem: the brute force is obvious, the optimal is a genuine aha, and the gap between them is where interviews are won. Work through it in layers — clarify, understand, spot the insight, then build the optimal solution in the Approaches below.
n − 1 edges for n nodes.graph[node] = [neighbours…]. The workhorse structure here.Before writing a line of code, spend two minutes narrowing the problem. Strong candidates ask sharp questions — interviewers at Amazon, Google and Meta explicitly score this.
“Is the input always a valid tree — connected and acyclic?”
If not, leaf-trimming breaks and you'd need cycle detection.
“Are node labels always 0 to n − 1?”
Arbitrary labels would force a hash map instead of a plain array.
“Can n be 1 with no edges?”
Critical case — no leaves, the loop never runs. Must be handled separately.
“What should I return for n = 2?”
Both nodes are leaves and both are valid answers. Confirms the stopping condition.
“Can the roots be returned in any order?”
A queue-based approach yields insertion order; sorting adds O(n log n) only if required.
“Return labels or node objects?”
The problem says integer labels — worth confirming.
“What is the maximum value of n?”
n up to 2 × 10⁴ means O(n²) is ~400M ops and risky — this pushes you toward O(n).
“Any memory limits?”
The adjacency list is O(n); good to confirm that's acceptable.
Before I start, I have a few clarifying questions.
First — is the input always a valid tree: connected and acyclic?
Second — are the edges undirected? I'll assume so unless told otherwise.
Third — what's the range of n? I want to know if O(n²) is acceptable or if I should aim for O(n).
And finally — should I handle n = 1 as a special case, where there are no edges?
Great. With those confirmed, let me walk through my approach.
In tree terms: pick a root so the height of the resulting rooted tree is as small as possible, and return all such roots.
Worked example 1 — n = 4, edges = [[1,0],[1,2],[1,3]]
0
|
2 — 1 — 3
root 0 → height 2
root 1 → height 1 ✓ minimum
root 2 → height 2
root 3 → height 2
answer: [1]
Worked example 2 — n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
0 1 2
\ | /
3
|
4
|
5
root 3 → height 2 ✓
root 4 → height 2 ✓
all others → height 3+
answer: [3, 4]
These three insights turn an O(n²) scan into an O(n) peel. Read them slowly — each builds on the last.
Consider the diameter — the longest path in the tree. Its midpoint minimises the maximum distance to the ends. An odd-length diameter has one middle node; an even-length diameter has two. Since a tree has exactly one path between any two nodes, the diameter is unique — so there can never be 3 or more centers.
odd diameter: A — B — C — D — E even diameter: A — B — C — D — E — F
^ ^---^
center = C (1) centers = C, D (2)A leaf has degree 1 — it sits at the very edge of the country. Root the tree at a leaf and there is always a longer path heading inward through its single neighbour. So a leaf can never be optimal — the only exception is n = 1, where the lone node is both a leaf and the answer.
Here is the leap. If you repeatedly remove all current leaves at once, the survivors converge on the center. It's onion-peeling: strip the outer layer, a new layer of leaves appears, strip again — until only the core is left.
start: 0 — 1 — 2 — 3 — 4 start: 0 — 1 — 2 — 3 — 4 — 5 round 1: 1 — 2 — 3 (−0, −4) round 1: 1 — 2 — 3 — 4 (−0, −5) round 2: 2 (−1, −3) round 2: 2 — 3 (−1, −4) answer: [2] answer: [2, 3]
| Brute force | Optimal | |
|---|---|---|
| Idea | BFS height from every root | Peel leaf layers to the center |
| Time | O(n²) | O(n) |
| Space | O(n) | O(n) |
| n = 20,000 | ~400M ops ✗ | ~20K ops ✓ |
The full code for both — with dry runs and the common mistakes to avoid — is in the Approaches selector below.
Key takeaway
The answer is always the center(s) of the tree — 1 or 2 nodes. Find them by repeatedly trimming all degree-1 leaves, layer by layer, until 2 or fewer nodes remain. Linear time, linear space.
1. build adjacency list + degree array
2. queue ← all degree-1 nodes (initial leaves)
3. remaining ← n
4. while remaining > 2:
batch = current leaves
remaining -= batch size
for each leaf in batch:
for each neighbour: degree--; if degree == 1: add to next batch
5. return whatever remains (the center nodes)