Minimum Height Trees
Description
A tree is an undirected graph in which any two vertices are connected by exactly one path — equivalently, a connected graph with no cycles.
You are given a tree of n nodes labelled from 0 to n - 1, defined by an array of n - 1 undirected edges. You may choose any node as the root. Different root choices produce trees of different heights (the number of edges on the longest downward path from root to a leaf).
Your task: find all nodes that, when chosen as root, give the minimum possible height. These are called the roots of Minimum Height Trees (MHTs).
The key insight is that the best root is always at the center of the tree. Think of stretching a tree out like a rope — the center of the rope minimizes the maximum distance to either end. A tree always has either 1 or 2 center nodes (never more, because 3+ centers would imply a cycle).
Examples
Example 1
Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation:
The tree looks like a star with node 1 at the center connected to nodes 0, 2, and 3.
- Root at 0: height = 2 (path 0→1→2 or 0→1→3)
- Root at 1: height = 1 (paths 1→0, 1→2, 1→3 all have length 1)
- Root at 2: height = 2 (path 2→1→0 or 2→1→3)
- Root at 3: height = 2 (path 3→1→0 or 3→1→2)
Node 1 achieves the minimum height of 1. It is the only MHT root.
Example 2
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3, 4]
Explanation:
The tree structure is:
0 1 2
\ | /
3
|
4
|
5
- Root at 3: height = 2 (path 3→4→5)
- Root at 4: height = 2 (path 4→3→0, 4→3→1, or 4→3→2)
- Root at 0: height = 3 (path 0→3→4→5)
- Root at 5: height = 3 (path 5→4→3→0)
Both nodes 3 and 4 achieve the minimum height of 2. The tree has two center nodes because the longest path (diameter) has even length.
Constraints
- 1 ≤ n ≤ 2 × 10⁴
- edges.length == n - 1
- 0 ≤ aᵢ, bᵢ < n
- aᵢ ≠ bᵢ
- All pairs (aᵢ, bᵢ) are distinct
- The given input is guaranteed to be a tree (connected, no cycles, no repeated edges)
Editorial
Brute Force
Intuition
The most straightforward approach is: try every node as the root, compute the tree height for each, and return the node(s) that achieve the minimum height.
How do we compute the height of a tree rooted at node r? Run a BFS (or DFS) from r. The height is the number of BFS levels minus one — equivalently, the maximum distance from r to any other node.
We do this for every node, track the minimum height seen, and collect all nodes that achieve it.
This approach requires no clever insight — it directly implements the problem statement. Its simplicity makes it a good starting point, but it repeats a lot of work since BFS traversals share structure.
Step-by-Step Explanation
Let's trace through with n = 4, edges = [[1,0],[1,2],[1,3]]:
Step 1: Build the adjacency list:
- 0: [1]
- 1: [0, 2, 3]
- 2: [1]
- 3: [1]
Step 2: Try root = 0. Run BFS from 0:
- Level 0: {0}
- Level 1: {1} (neighbor of 0)
- Level 2: {2, 3} (neighbors of 1, excluding visited 0)
- Height = 2.
Step 3: Try root = 1. Run BFS from 1:
- Level 0: {1}
- Level 1: {0, 2, 3} (all neighbors of 1)
- No more levels. Height = 1.
Step 4: Try root = 2. Run BFS from 2:
- Level 0: {2}
- Level 1: {1} (neighbor of 2)
- Level 2: {0, 3} (neighbors of 1, excluding visited 2)
- Height = 2.
Step 5: Try root = 3. Similarly, height = 2.
Step 6: Minimum height = 1, achieved only by node 1. Return [1].
Algorithm
- Build the adjacency list from the edge list.
- For each node
rfrom 0 to n-1:
a. Run BFS fromr. Count the number of levels.
b. Height of tree rooted atr= (number of BFS levels) - 1.
c. Record height[r]. - Find the minimum value in the height array.
- Return all nodes whose height equals the minimum.
Code
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if (n == 1) return {0};
// Build adjacency list
vector<vector<int>> adj(n);
for (auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
// Compute height for each root using BFS
int minHeight = n; // upper bound
vector<int> heights(n);
for (int root = 0; root < n; root++) {
vector<bool> visited(n, false);
queue<int> q;
q.push(root);
visited[root] = true;
int height = -1;
while (!q.empty()) {
int sz = q.size();
height++;
for (int i = 0; i < sz; i++) {
int node = q.front(); q.pop();
for (int next : adj[node]) {
if (!visited[next]) {
visited[next] = true;
q.push(next);
}
}
}
}
heights[root] = height;
minHeight = min(minHeight, height);
}
// Collect all roots with minimum height
vector<int> result;
for (int i = 0; i < n; i++) {
if (heights[i] == minHeight) result.push_back(i);
}
return result;
}
};from collections import deque
class Solution:
def findMinHeightTrees(self, n: int, edges: list[list[int]]) -> list[int]:
if n == 1:
return [0]
# Build adjacency list
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
def bfs_height(root: int) -> int:
visited = [False] * n
queue = deque([root])
visited[root] = True
height = -1
while queue:
height += 1
for _ in range(len(queue)):
node = queue.popleft()
for neighbor in adj[node]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
return height
# Compute height for each possible root
heights = [bfs_height(r) for r in range(n)]
min_height = min(heights)
return [i for i in range(n) if heights[i] == min_height]class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) return List.of(0);
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
int minHeight = n;
int[] heights = new int[n];
for (int root = 0; root < n; root++) {
boolean[] visited = new boolean[n];
Queue<Integer> queue = new LinkedList<>();
queue.offer(root);
visited[root] = true;
int height = -1;
while (!queue.isEmpty()) {
int sz = queue.size();
height++;
for (int i = 0; i < sz; i++) {
int node = queue.poll();
for (int next : adj.get(node)) {
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
}
}
}
heights[root] = height;
minHeight = Math.min(minHeight, height);
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (heights[i] == minHeight) result.add(i);
}
return result;
}
}Complexity Analysis
Time Complexity: O(n²)
We run BFS from each of the n nodes. Each BFS visits all n nodes and traverses all n-1 edges, taking O(n) time. Total: n × O(n) = O(n²). With n up to 2×10⁴, this is 4×10⁸ operations — likely too slow.
Space Complexity: O(n)
The adjacency list takes O(n) space (n-1 edges, each stored twice = O(n)). Each BFS uses O(n) for the visited array and queue. The heights array is O(n). Total: O(n).
Why This Approach Is Not Efficient
The brute force runs n separate BFS traversals, each costing O(n), for a total of O(n²). With n up to 20,000, that's 400 million operations — too slow for competitive programming time limits.
The core inefficiency is redundant traversal. When we BFS from node 0, we discover the distances from 0 to every other node. When we BFS from node 1, we recompute almost the same information. The structure of the tree doesn't change between roots — we are repeating work.
Instead of asking "what is the height from each root?", we can flip the question: which nodes are at the center of the tree? The center of a tree is the node(s) that minimize the maximum distance to any leaf. We can find the center in O(n) time by peeling off leaves layer by layer — like peeling an onion from the outside in. The last remaining node(s) are the center(s), and they are exactly the MHT roots.
Optimal Approach - Topological Leaf Peeling
Intuition
Picture the tree as a physical object — a molecule, or a network of strings pinned to a board. Leaves are the nodes on the very outside, with only one connection. If we pick a leaf as root, the tree will be very tall because everything else hangs below it. Leaves are the worst roots.
Now imagine "trimming" all leaves simultaneously — snipping every node that has only one connection. After this trim, some inner nodes that previously had 2+ connections now become the new leaves (because their old leaf neighbors were removed). We trim again. And again.
Each round of trimming peels one layer off the outside. Eventually, only 1 or 2 nodes remain. These are the center of the tree:
- If the tree's longest path (diameter) has odd length → 1 center node.
- If the diameter has even length → 2 center nodes.
Why does this work? Because trimming from all sides simultaneously is like moving inward symmetrically. The last node(s) standing are equidistant from all the furthest extremities — exactly the nodes that minimize the maximum distance (height) when chosen as root.
This is essentially topological sort on a tree: we start with all degree-1 nodes (leaves) and peel inward, just like Kahn's algorithm starts with in-degree-0 nodes.
A tree can have at most 2 center nodes. If it had 3 or more, they would form a cycle, contradicting the tree property.
Step-by-Step Explanation
Let's trace through with n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]:
Tree structure:
0 1 2
\ | /
3
|
4
|
5
Step 1: Build adjacency list and compute degrees:
- Node 0: neighbors=[3], degree=1 → leaf!
- Node 1: neighbors=[3], degree=1 → leaf!
- Node 2: neighbors=[3], degree=1 → leaf!
- Node 3: neighbors=[0,1,2,4], degree=4
- Node 4: neighbors=[3,5], degree=2
- Node 5: neighbors=[4], degree=1 → leaf!
Initial leaf queue: [0, 1, 2, 5]. These 4 nodes each have degree 1.
Step 2: First peeling round — process all 4 leaves:
- Remove 0: degree[3] drops from 4 to 3.
- Remove 1: degree[3] drops from 3 to 2.
- Remove 2: degree[3] drops from 2 to 1 → Node 3 becomes a new leaf!
- Remove 5: degree[4] drops from 2 to 1 → Node 4 becomes a new leaf!
New leaf queue: [3, 4]. Remaining nodes: {3, 4}.
Step 3: Second peeling round — process nodes 3 and 4:
- Remove 3: degree[4] drops from 1 to 0.
- Remove 4: degree[3] drops from 1 to 0.
New leaf queue: empty. Last layer was [3, 4].
Step 4: Return the last layer: [3, 4]. These are the MHT roots, each giving height 2.
Topological Leaf Peeling — Finding MHT Roots — Watch as leaves are peeled layer by layer from the outside of the tree. The last remaining nodes are the centers — the optimal roots for Minimum Height Trees.
Algorithm
- Edge case: If n == 1, return [0].
- Build the graph: Create an adjacency list. Compute the degree of each node.
- Initialize leaf queue: Add all nodes with degree == 1 to a queue.
- Peel leaves layer by layer:
a. Clear thelast_layerlist.
b. Process all nodes currently in the queue (one full BFS level):- Dequeue a leaf node. Add it to
last_layer. - For each neighbor of this leaf: decrement its degree by 1.
- If the neighbor's degree becomes 1, it's a new leaf — add to queue.
c. Repeat until the queue is empty.
- Dequeue a leaf node. Add it to
- Return
last_layer. The last set of nodes processed are the center(s) of the tree — the MHT roots. There will be either 1 or 2 nodes.
Code
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if (n == 1) return {0};
// Build adjacency list and compute degrees
vector<vector<int>> adj(n);
vector<int> degree(n, 0);
for (auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
degree[e[0]]++;
degree[e[1]]++;
}
// Initialize queue with all leaves (degree == 1)
queue<int> q;
for (int i = 0; i < n; i++) {
if (degree[i] == 1) q.push(i);
}
// Peel leaves layer by layer
vector<int> lastLayer;
while (!q.empty()) {
lastLayer.clear();
int sz = q.size();
for (int i = 0; i < sz; i++) {
int leaf = q.front(); q.pop();
lastLayer.push_back(leaf);
for (int neighbor : adj[leaf]) {
degree[neighbor]--;
if (degree[neighbor] == 1) {
q.push(neighbor);
}
}
}
}
return lastLayer;
}
};from collections import deque
class Solution:
def findMinHeightTrees(self, n: int, edges: list[list[int]]) -> list[int]:
if n == 1:
return [0]
# Build adjacency list and compute degrees
adj = [[] for _ in range(n)]
degree = [0] * n
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
degree[a] += 1
degree[b] += 1
# Initialize queue with all leaves
queue = deque(i for i in range(n) if degree[i] == 1)
# Peel leaves layer by layer
last_layer = []
while queue:
last_layer.clear()
for _ in range(len(queue)):
leaf = queue.popleft()
last_layer.append(leaf)
for neighbor in adj[leaf]:
degree[neighbor] -= 1
if degree[neighbor] == 1:
queue.append(neighbor)
return last_layerclass Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) return List.of(0);
// Build adjacency list and compute degrees
List<List<Integer>> adj = new ArrayList<>();
int[] degree = new int[n];
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
degree[e[0]]++;
degree[e[1]]++;
}
// Initialize queue with all leaves
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (degree[i] == 1) queue.offer(i);
}
// Peel leaves layer by layer
List<Integer> lastLayer = new ArrayList<>();
while (!queue.isEmpty()) {
lastLayer.clear();
int sz = queue.size();
for (int i = 0; i < sz; i++) {
int leaf = queue.poll();
lastLayer.add(leaf);
for (int neighbor : adj.get(leaf)) {
degree[neighbor]--;
if (degree[neighbor] == 1) {
queue.offer(neighbor);
}
}
}
}
return lastLayer;
}
}Complexity Analysis
Time Complexity: O(n)
Building the adjacency list and degree array takes O(n) since there are n-1 edges. The leaf peeling loop processes each node exactly once (each node enters the queue at most once and is dequeued once). For each node, we update the degrees of its neighbors — across all iterations, this touches each edge exactly twice (once from each endpoint). Total edge work: O(n). Overall: O(n).
This is a massive improvement over the brute force O(n²). With n = 20,000, we go from 400 million operations to just 20,000.
Space Complexity: O(n)
The adjacency list stores n-1 edges (each stored twice) = O(n). The degree array is O(n). The queue holds at most O(n) nodes. The last_layer list is at most O(n) during processing (but the final result is at most 2 nodes). Total: O(n).