Minimum Height Trees — Solution in Python, Java & C++
Minimum Height Trees solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Height Trees is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Graph, Topological Sort
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A tree has n nodes labelled 0 through n - 1 and n - 1 undirected edges. Rooting it at any node produces a tree of some height.
Return every root that yields the minimum possible height, in ascending order.
Example 1
Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Example 2
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]
Example 3
Input: n = 1, edges = []
Output: [0]
Constraints
1 <= n <= 40edges.length == n - 1The input is guaranteed to be a tree.
Follow-up: There are at most two answers. Why can there never be three?
Hints for Minimum Height Trees
Hint 1
The best roots sit at the centre of the tree's longest path, so peel inward from the outside.
Hint 2
Repeatedly strip off all current leaves, exactly like a topological sort on an undirected tree.
Hint 3
Stop when 2 or fewer nodes remain — those are the centroids.
How to solve Minimum Height Trees
Peel leaves layer by layer; the last one or two nodes standing are the centroids, which root the minimum-height trees.
Approach
- Return
[0]forn = 1. - Compute degrees; start with all degree-1 nodes as leaves.
- While more than 2 nodes remain, remove the leaves and collect neighbours whose degree drops to 1.
- Return the remaining nodes.
Why it works
The minimum-height root lies at the middle of every longest path; stripping leaves from all ends simultaneously shortens every longest path equally, so the survivors are the middle one (odd length) or two (even length).
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Rooting at each node and measuring is
O(n²).
Reference solution
Python
def findMinHeightTrees(n: int, edges):
if n == 1:
return [0]
adjacency = [[] for _ in range(n)]
degree = [0] * n
for a, b in edges:
adjacency[a].append(b)
adjacency[b].append(a)
degree[a] += 1
degree[b] += 1
leaves = [i for i in range(n) if degree[i] == 1]
remaining = n
while remaining > 2:
remaining -= len(leaves)
nxt = []
for leaf in leaves:
for neighbour in adjacency[leaf]:
degree[neighbour] -= 1
if degree[neighbour] == 1:
nxt.append(neighbour)
leaves = nxt
return sorted(leaves)Java
public static int[] findMinHeightTrees(int n, int[][] edges) {
if (n == 1) return new int[]{0};
List<List<Integer>> adjacency = new ArrayList<>();
int[] degree = new int[n];
for (int i = 0; i < n; i++) adjacency.add(new ArrayList<>());
for (int[] e : edges) {
adjacency.get(e[0]).add(e[1]);
adjacency.get(e[1]).add(e[0]);
degree[e[0]]++;
degree[e[1]]++;
}
List<Integer> leaves = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (degree[i] == 1) leaves.add(i);
}
int remaining = n;
while (remaining > 2) {
remaining -= leaves.size();
List<Integer> next = new ArrayList<>();
for (int leaf : leaves) {
for (int neighbour : adjacency.get(leaf)) {
degree[neighbour]--;
if (degree[neighbour] == 1) next.add(neighbour);
}
}
leaves = next;
}
Collections.sort(leaves);
int[] out = new int[leaves.size()];
for (int i = 0; i < leaves.size(); i++) out[i] = leaves.get(i);
return out;
}C++
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if (n == 1) return vector<int>{0};
vector<vector<int>> adjacency(n);
vector<int> degree(n, 0);
for (const auto& e : edges) {
adjacency[e[0]].push_back(e[1]);
adjacency[e[1]].push_back(e[0]);
degree[e[0]]++;
degree[e[1]]++;
}
vector<int> leaves;
for (int i = 0; i < n; i++) {
if (degree[i] == 1) leaves.push_back(i);
}
int remaining = n;
while (remaining > 2) {
remaining -= (int) leaves.size();
vector<int> next;
for (int leaf : leaves) {
for (int neighbour : adjacency[leaf]) {
degree[neighbour]--;
if (degree[neighbour] == 1) next.push_back(neighbour);
}
}
leaves = next;
}
sort(leaves.begin(), leaves.end());
return leaves;
}JavaScript
var findMinHeightTrees = function(n, edges) {
if (n === 1) return [0];
const adjacency = [];
const degree = [];
for (let i = 0; i < n; i++) {
adjacency.push([]);
degree.push(0);
}
for (let i = 0; i < edges.length; i++) {
adjacency[edges[i][0]].push(edges[i][1]);
adjacency[edges[i][1]].push(edges[i][0]);
degree[edges[i][0]]++;
degree[edges[i][1]]++;
}
let leaves = [];
for (let i = 0; i < n; i++) {
if (degree[i] === 1) leaves.push(i);
}
let remaining = n;
while (remaining > 2) {
remaining -= leaves.length;
const next = [];
for (let i = 0; i < leaves.length; i++) {
const leaf = leaves[i];
for (let j = 0; j < adjacency[leaf].length; j++) {
const neighbour = adjacency[leaf][j];
degree[neighbour]--;
if (degree[neighbour] === 1) next.push(neighbour);
}
}
leaves = next;
}
return leaves.slice().sort(function(a, b) { return a - b; });
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)