A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.
Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select 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 MHTs' root labels. 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.
Example 1:
Input: n = 4, edges = [[1,0],[1,2],[1,3]] Output: [1] Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.
Example 2:
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] Output: [3,4]
Constraints:
1 <= n <= 2 * 104edges.length == n - 10 <= ai, bi < nai != bi(ai, bi) are distinct.The Minimum Height Trees problem asks you to find all possible root nodes of an undirected tree that produce the smallest tree height. A key observation is that the roots of minimum height trees correspond to the center(s) of the tree. Instead of computing the height from every node (which would be inefficient), you can approach the problem using a topological trimming strategy.
Build an adjacency list and track the degree of each node. Nodes with degree 1 are leaves. Using a queue, iteratively remove these leaves level by level (similar to Breadth-First Search). Each round removes the outermost layer of the tree, gradually moving toward the center. Continue trimming until only one or two nodes remain—these are the valid roots of the minimum height trees.
This approach works because repeatedly removing leaves naturally exposes the tree’s centroid(s). The algorithm processes each node and edge only once, resulting in an efficient O(n) time complexity and O(n) space complexity.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Leaf Trimming using BFS (Topological Style) | O(n) | O(n) |
| Brute Force DFS/BFS from Every Node | O(n^2) | O(n) |
Algorithms Made Easy
Use these hints if you're stuck. Try solving on your own first.
How many MHTs can a graph have at most?
This approach uses an iterative method to trim the leaf nodes layer by layer until you are left with the centermost nodes, which are the roots of the Minimum Height Trees.
The idea is similar to peeling layers of an onion from the outside to the inside. The process stops when there are no more than two nodes left.
Time Complexity: O(n), since each node and edge is processed once.
Space Complexity: O(n), for storing edges and nodes’ degrees.
1#include <vector>
2#include <queue>
3using namespace std;
4
5vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
6 if (n == 1) return {0};
7
8 vector<int> degree(n, 0);
9 vector<vector<int>> adj(n);
10
11 for (const auto& edge : edges) {
12 adj[edge[0]].push_back(edge[1]);
13 adj[edge[1]].push_back(edge[0]);
14 degree[edge[0]]++;
15 degree[edge[1]]++;
16 }
17
18 queue<int> leaves;
19 for (int i = 0; i < n; i++) {
20 if (degree[i] == 1) leaves.push(i);
21 }
22
23 int count = n;
24 while (count > 2) {
25 int size = leaves.size();
26 count -= size;
27
28 for (int i = 0; i < size; i++) {
29 int leaf = leaves.front();
30 leaves.pop();
31 degree[leaf]--;
32
33 for (int neighbor : adj[leaf]) {
34 if (--degree[neighbor] == 1) {
35 leaves.push(neighbor);
36 }
37 }
38 }
39 }
40
41 vector<int> result;
42 while (!leaves.empty()) {
43 result.push_back(leaves.front());
44 leaves.pop();
45 }
46
47 return result;
48}
49The C++ code uses a queue to iteratively remove leaves, reducing the graph till potential centroids are found. It leverages vectors for adjacency list creation and manages the node degree.
This technique applies two breadth-first searches (BFS). Start from any node, find the farthest node to determine a tree diameter. From this end node, perform another BFS to determine the second endpoint. The center of the path between these endpoints, which are the potential MHT roots, is found.
Time Complexity: O(n), for initializing and iterating over nodes.
Space Complexity: O(n), due to graph adjacency representations and queue processing.
1import java.util.*;
2
3
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Minimum Height Trees is a common medium-level graph problem discussed in coding interviews. It tests understanding of graph representations, BFS, and the concept of tree centers using topological-style processing.
In any tree, the center is either a single node or two adjacent nodes depending on the tree’s diameter length. These nodes minimize the maximum distance to all other nodes, which leads to the smallest possible height.
The optimal approach is to iteratively remove leaf nodes using a BFS-style topological process. By trimming leaves layer by layer, the algorithm converges to the tree’s center nodes, which form the roots of minimum height trees. This approach runs in O(n) time.
An adjacency list is ideal for representing the graph, along with a queue to process leaf nodes during BFS. A degree array or map is also used to track how many neighbors each node has while trimming leaves.
In the Java solution, adjacency sets represent connections with degree checks for leaves. The while loop prunes tree leaves iteratively until potential centroids, interpreted as MHTs, are left.