Minimum Height Trees
Medium · Graphs · Explanation and code example
Topological Sorting (BFS)
How it works
Imagine peeling the tree like an onion, removing leaves layer by layer. The nodes that remain at the very end (when only 1 or 2 nodes are left) must be the centroids, since they're the innermost points of the tree.
Each round of removal brings us one step closer to the center. Since a tree can have at most 2 centroids (on a diameter of odd length), we stop when 2 or fewer nodes remain.
Steps
- Build an adjacency list and track each node's edge count (degree).
- Initialize a queue with all leaf nodes (degree =
1), excluding the special case wheren = 1. - While more than
2nodes remain:- Remove all current leaves from the queue.
- For each removed leaf, decrement its neighbor's degree.
- If a neighbor becomes a leaf, add it to the queue.
- The remaining nodes in the queue are the minimum height tree roots.
Complexity
- Time complexity:
O(V + E) - Space complexity:
O(V)
Where
Vis the number of vertices andEis the number of edges.
Things to watch for
Forgetting the Single Node Edge Case
When n = 1, there are no edges and the only node 0 is trivially the root of a minimum height tree. Many solutions fail to handle this case, leading to empty results or index errors when trying to process an empty edge list.
Using a Visited Set Instead of Parent Tracking in DFS
In tree traversal, using a full visited set is unnecessary overhead. Since trees have no cycles, simply passing the parent node to avoid revisiting the previous node is sufficient and more efficient. Using a visited set can also cause issues if not cleared properly between multiple DFS calls.
Incorrectly Implementing Leaf Removal in Topological Sort
When peeling leaves layer by layer, a common mistake is modifying the degree array while iterating over the current batch of leaves. This can cause nodes to be processed prematurely or skipped entirely. Always process all current-level leaves before updating degrees for the next level.
Python code example
from typing import List
from collections import defaultdict, deque
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if n == 1:
return [0]
adj = defaultdict(list)
for n1, n2 in edges:
adj[n1].append(n2)
adj[n2].append(n1)
edge_cnt = {}
leaves = deque()
for src, neighbors in adj.items():
edge_cnt[src] = len(neighbors)
if len(neighbors) == 1:
leaves.append(src)
while leaves:
if n <= 2:
return list(leaves)
for _ in range(len(leaves)):
node = leaves.popleft()
n -= 1
for nei in adj[node]:
edge_cnt[nei] -= 1
if edge_cnt[nei] == 1:
leaves.append(nei)
C++ code example
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if (n == 1) return {0};
vector<vector<int>> adj(n);
for (auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
vector<int> edge_cnt(n);
queue<int> leaves;
for (int i = 0; i < n; ++i) {
edge_cnt[i] = adj[i].size();
if (adj[i].size() == 1)
leaves.push(i);
}
while (!leaves.empty()) {
if (n <= 2) {
vector<int> result;
while (!leaves.empty()) {
result.push_back(leaves.front());
leaves.pop();
}
return result;
}
int size = leaves.size();
for (int i = 0; i < size; ++i) {
int node = leaves.front();
leaves.pop();
--n;
for (int& nei : adj[node]) {
--edge_cnt[nei];
if (edge_cnt[nei] == 1)
leaves.push(nei);
}
}
}
return {};
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.