Topological Sort — Minimum Height Trees
↗ LeetCode: Minimum Height Trees · Medium · pattern chapter →
Asked atAmazonGoogleMeta
Given an undirected tree of n nodes, return all nodes that when picked as root give minimum height tree. At most 2 exist.
Example 1 — n=4, edges=[[1,0],[1,2],[1,3]] → [1]Example 2 — n=6, edges=[[3,0],[3,1],[3,2],[3,4],[5,4]] → [3,4]
Constraints — 1 ≤ n ≤ 2·10⁴. Brute runs BFS from every node — O(n²) = 10⁸ ops at n=2·10⁴ (TLE). Peel leaves layer by layer (there are 1-2 centroids) is O(n) = 2·10⁴ ops.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Try each node as root, BFS
O(n²). TLE at n=2·10⁴.
Approach 2 — Peel leaves inward (canonical topological peeling)
Insight. MHT roots are always at the center(s) of the tree — 1 or 2 nodes. Repeatedly remove leaves (degree-1 nodes) layer by layer. The last remaining 1 or 2 nodes are the answer.
java
List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) return List.of(0);
List<Set<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new HashSet<>());
for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
List<Integer> leaves = new ArrayList<>();
for (int i = 0; i < n; i++) if (g.get(i).size() == 1) leaves.add(i);
int remaining = n;
while (remaining > 2) {
remaining -= leaves.size();
List<Integer> next = new ArrayList<>();
for (int leaf : leaves) {
int parent = g.get(leaf).iterator().next();
g.get(parent).remove(leaf);
if (g.get(parent).size() == 1) next.add(parent);
}
leaves = next;
}
return leaves;
}Execution Trace
Step 1 / 2initial leaves
Complexity — Time O(n); Space O(n).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| BFS from each root | O(n²) | O(n) | baseline |
| Peel leaves | O(n) | O(n) | canonical |
When to use which
- Tree center problems → leaf peeling.
- General graph center → different — use eccentricity / all-pairs BFS.
- "Return the actual height" → 2-BFS: BFS from any node to find farthest u; BFS from u to find diameter.
AI Study CompanionBeta
Related problems
- Course Schedule — general graph toposort
- Tree Diameter
- Longest Path in Tree
Was this page helpful?
📚 Related problems