Minimum Height Trees
MedPrompt
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- All the pairs
(ai, bi)are distinct. - The given input is guaranteed to be a tree and there will be no repeated edges.
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to iterate through every node, treat it as the root of the tree, and calculate the resulting tree's height. We keep track of the minimum height found so far and the list of nodes that achieve this height.
Algorithm
- Build an adjacency list representation of the tree.
- Initialize
min_heightto a very large value andmht_rootsto an empty list. - Loop through each node
ifrom0ton-1:- Consider
ias the root. - Perform a Breadth-First Search (BFS) starting from
ito find the height of the tree. The height is the number of levels in the BFS traversal. - If the calculated height
his less thanmin_height, updatemin_height = hand resetmht_rootsto[i]. - If
his equal tomin_height, additomht_roots.
- Consider
- After checking all nodes, return
mht_roots.
Walkthrough
This method exhaustively checks every possibility. For each node in the tree, we assume it's the root and then determine the height of the resulting rooted tree. The height is defined as the longest path from the root to any leaf node. This can be calculated using a graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS). A BFS is natural here, as the height corresponds to the number of levels traversed. We maintain a variable to store the minimum height seen so far and a list of corresponding roots. If we find a node that results in a smaller height, we update the minimum and clear the list, adding the new node. If we find a node that results in the same minimum height, we just add it to our list of results.
import java.util.*; class Solution { public List<Integer> findMinHeightTrees(int n, int[][] edges) { if (n == 1) { return Collections.singletonList(0); } List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } for (int[] edge : edges) { adj.get(edge[0]).add(edge[1]); adj.get(edge[1]).add(edge[0]); } int minHeight = Integer.MAX_VALUE; List<Integer> mhtRoots = new ArrayList<>(); for (int i = 0; i < n; i++) { int height = calculateHeight(i, n, adj); if (height < minHeight) { minHeight = height; mhtRoots.clear(); mhtRoots.add(i); } else if (height == minHeight) { mhtRoots.add(i); } } return mhtRoots; } private int calculateHeight(int root, int n, List<List<Integer>> adj) { Queue<Integer> queue = new LinkedList<>(); queue.offer(root); boolean[] visited = new boolean[n]; visited[root] = true; int height = -1; while (!queue.isEmpty()) { int levelSize = queue.size(); height++; for (int i = 0; i < levelSize; i++) { int u = queue.poll(); for (int v : adj.get(u)) { if (!visited[v]) { visited[v] = true; queue.offer(v); } } } } return height; }}Complexity
Time
O(N^2), where N is the number of nodes. For each of the N nodes, we perform a Breadth-First Search (BFS) to calculate the height, which takes O(N + E) = O(N) time (since E = N-1 for a tree). This results in a total time complexity of O(N * N) = O(N^2).
Space
O(N), where N is the number of nodes. We need O(N) space for the adjacency list and another O(N) for the data structures used in each BFS call (queue and visited array).
Trade-offs
Pros
Simple to understand and implement.
Guaranteed to be correct if it runs within the time limit.
Cons
Highly inefficient due to its quadratic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints (n up to 2 * 10^4).
A more efficient approach is based on the property that the roots of Minimum Height Trees are the center(s) of the graph. The center(s) of a tree are the middle node(s) of its longest path. We can find a longest path by performing two tree traversals (like BFS or DFS).
Algorithm
- Build an adjacency list for the tree.
- Step 1: Find an endpoint of a longest path.
- Start a BFS/DFS from an arbitrary node (e.g., node 0).
- Find the node
Athat is farthest from the starting node. This nodeAis guaranteed to be one of the endpoints of a longest path in the tree.
- Step 2: Find the longest path.
- Start a second BFS/DFS from node
A. - Find the node
Bthat is farthest fromA. The path betweenAandBis a longest path. - During this second traversal, keep track of parent pointers to be able to reconstruct the path.
- Start a second BFS/DFS from node
- Step 3: Find the center(s).
- Reconstruct the longest path from
Bback toAusing the parent pointers. - If the path has an odd number of nodes, the single middle node is the MHT root.
- If the path has an even number of nodes, the two middle nodes are the MHT roots.
- Reconstruct the longest path from
Walkthrough
This method leverages a key insight about tree structures. Instead of calculating height from every node, we find the single longest path (also called the diameter) of the tree. The node or nodes that lie in the middle of this path will minimize the maximum distance to any other node in the tree, thus forming the roots of the MHTs. The algorithm to find this path involves two BFS runs:
- The first BFS starts from any node and finds the node (
A) at the greatest distance. This nodeAis guaranteed to be an endpoint of at least one longest path. - The second BFS starts from
Aand finds the node (B) at the greatest distance from it. The path fromAtoBis a longest path in the tree. Once we have this path, we can easily find its midpoint(s) to get our answer.
import java.util.*; class Solution { public List<Integer> findMinHeightTrees(int n, int[][] edges) { if (n <= 1) { return Collections.singletonList(0); } List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } for (int[] edge : edges) { adj.get(edge[0]).add(edge[1]); adj.get(edge[1]).add(edge[0]); } // 1. Find one endpoint of a longest path int[] parent = new int[n]; int[] dist = new int[n]; bfs(0, n, adj, parent, dist); int endpoint1 = 0; for (int i = 0; i < n; i++) { if (dist[i] > dist[endpoint1]) { endpoint1 = i; } } // 2. Find the other endpoint and the longest path bfs(endpoint1, n, adj, parent, dist); int endpoint2 = 0; for (int i = 0; i < n; i++) { if (dist[i] > dist[endpoint2]) { endpoint2 = i; } } // 3. Reconstruct the longest path List<Integer> path = new ArrayList<>(); int curr = endpoint2; while (curr != -1) { path.add(curr); curr = parent[curr]; } // 4. Find the center(s) int pathLength = path.size(); if (pathLength % 2 == 1) { return Collections.singletonList(path.get(pathLength / 2)); } else { return Arrays.asList(path.get(pathLength / 2 - 1), path.get(pathLength / 2)); } } private void bfs(int startNode, int n, List<List<Integer>> adj, int[] parent, int[] dist) { Arrays.fill(parent, -1); Arrays.fill(dist, -1); Queue<Integer> queue = new LinkedList<>(); queue.offer(startNode); dist[startNode] = 0; while (!queue.isEmpty()) { int u = queue.poll(); for (int v : adj.get(u)) { if (dist[v] == -1) { dist[v] = dist[u] + 1; parent[v] = u; queue.offer(v); } } } }}Complexity
Time
O(N), where N is the number of nodes. The algorithm consists of building an adjacency list (O(N)), two BFS traversals (each O(N)), and path reconstruction (O(N)). The total time is linear.
Space
O(N). Space is required for the adjacency list (O(N)), the BFS queue (O(N)), and arrays to store distances and parent pointers (O(N)).
Trade-offs
Pros
Optimal O(N) time complexity.
Correctly identifies the center(s) of the tree by finding the longest path.
Cons
The implementation is more involved than the leaf-peeling approach, requiring two separate traversals and path reconstruction logic.
The proof of why this works (i.e., why the farthest node from an arbitrary node is an endpoint of a longest path) is not immediately obvious.
The most elegant and efficient solution involves iteratively removing the leaves of the tree. The intuition is that the nodes we are looking for must be the most 'central' ones. By repeatedly 'peeling' away the outermost layer of nodes (the leaves), we move closer to the center. The process continues until we are left with either one or two nodes, which are the roots of the MHTs.
Algorithm
- Handle the base case: if
n <= 2, all nodes are MHT roots. - Build an adjacency list and an array to store the degree of each node.
- Initialize a queue and add all leaf nodes (nodes with degree 1) to it.
- Keep track of the number of nodes remaining in the graph, initially
n. - While the number of remaining nodes is greater than 2:
- Process all nodes currently in the leaf queue (this constitutes one layer).
- For each leaf node removed:
- Decrement the degree of its single neighbor.
- If the neighbor's degree becomes 1, it is a new leaf, so add it to the queue for the next iteration.
- The loop terminates when 1 or 2 nodes are left. These nodes are the last ones to be processed and are the MHT roots remaining in the queue.
Walkthrough
This approach is analogous to a topological sort. The key idea is that the nodes that are furthest from the center are the leaves of the tree. If we remove all leaves, the new leaves of the remaining graph are the nodes that were next to the original leaves. We can continue this process, removing layers of leaves, until we are left with the most central nodes. This process will always terminate with either one node (if the longest path has an odd number of nodes) or two adjacent nodes (if the longest path has an even number of nodes). These final remaining nodes are the roots of the Minimum Height Trees.
import java.util.*; class Solution { public List<Integer> findMinHeightTrees(int n, int[][] edges) { if (n <= 2) { List<Integer> result = new ArrayList<>(); for (int i = 0; i < n; i++) { result.add(i); } return result; } List<List<Integer>> adj = new ArrayList<>(); int[] degrees = new int[n]; for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } for (int[] edge : edges) { int u = edge[0]; int v = edge[1]; adj.get(u).add(v); adj.get(v).add(u); degrees[u]++; degrees[v]++; } Queue<Integer> leaves = new LinkedList<>(); for (int i = 0; i < n; i++) { if (degrees[i] == 1) { leaves.offer(i); } } int remainingNodes = n; while (remainingNodes > 2) { int leavesCount = leaves.size(); remainingNodes -= leavesCount; for (int i = 0; i < leavesCount; i++) { int leaf = leaves.poll(); for (int neighbor : adj.get(leaf)) { degrees[neighbor]--; if (degrees[neighbor] == 1) { leaves.offer(neighbor); } } } } return new ArrayList<>(leaves); }}Complexity
Time
O(N), where N is the number of nodes. Building the graph and initial degrees takes O(N + E) = O(N). Each node and edge is processed exactly once during the leaf removal process. Thus, the overall time complexity is linear.
Space
O(N). We use an adjacency list (O(N)), a degree array (O(N)), and a queue that can store up to N-1 nodes in the worst case (a star graph).
Trade-offs
Pros
Optimal O(N) time complexity.
Conceptually elegant and often considered easier to implement correctly than the longest path method.
Directly finds the centers without explicit path reconstruction.
Cons
The intuition might not be as immediately obvious as the brute-force method, but it's a standard graph algorithm pattern.
Solutions
Solution
class Solution { public List < Integer > findMinHeightTrees ( int n , int [][] edges ) { if ( n == 1 ) { return Collections . singletonList ( 0 ); } List < Integer >[] g = new List [ n ]; Arrays . setAll ( g , k -> new ArrayList <>()); int [] degree = new int [ n ]; for ( int [] e : edges ) { int a = e [ 0 ], b = e [ 1 ]; g [ a ]. add ( b ); g [ b ]. add ( a ); ++ degree [ a ]; ++ degree [ b ]; } Queue < Integer > q = new LinkedList <>(); for ( int i = 0 ; i < n ; ++ i ) { if ( degree [ i ] == 1 ) { q . offer ( i ); } } List < Integer > ans = new ArrayList <>(); while (! q . isEmpty ()) { ans . clear (); for ( int i = q . size (); i > 0 ; -- i ) { int a = q . poll (); ans . add ( a ); for ( int b : g [ a ]) { if (-- degree [ b ] == 1 ) { q . offer ( b ); } } } } return ans ; } }class Solution { public: vector < int > findMinHeightTrees ( int n , vector < vector < int >>& edges ) { if ( n == 1 ) return { 0 }; vector < vector < int >> g ( n ); vector < int > degree ( n ); for ( auto & e : edges ) { int a = e [ 0 ], b = e [ 1 ]; g [ a ]. push_back ( b ); g [ b ]. push_back ( a ); ++ degree [ a ]; ++ degree [ b ]; } queue < int > q ; for ( int i = 0 ; i < n ; ++ i ) if ( degree [ i ] == 1 ) q . push ( i ); vector < int > ans ; while ( ! q . empty ()) { ans . clear (); for ( int i = q . size (); i > 0 ; -- i ) { int a = q . front (); q . pop (); ans . push_back ( a ); for ( int b : g [ a ]) if ( -- degree [ b ] == 1 ) q . push ( b ); } } return ans ; } };from typing import List , Set from collections import defaultdict class Solution : def findMinHeightTrees ( self , n : int , edges : List [ List [ int ]]) -> List [ int ]: if n == 1 : return [ 0 ] graph = defaultdict ( set ) for a , b in edges : graph [ a ]. add ( b ) graph [ b ]. add ( a ) # just check neighbours[] size, not indgree[] for each node leaves = [ i for i in range ( n ) if len ( graph [ i ]) == 1 ] while n > 2 : n -= len ( leaves ) new_leaves = [] for leaf in leaves : # should be only one in hashset pop(), because it's a leaf node neighbor = graph [ leaf ]. pop () graph [ neighbor ]. remove ( leaf ) if len ( graph [ neighbor ]) == 1 : new_leaves . append ( neighbor ) leaves = new_leaves return leaves ############### class Solution : def findMinHeightTrees ( self , n : int , edges : List [ List [ int ]]) -> List [ int ]: if n == 1 : return [ 0 ] g = defaultdict ( list ) degree = [ 0 ] * n for a , b in edges : g [ a ]. append ( b ) g [ b ]. append ( a ) degree [ a ] += 1 # not needed, just len(g[a]) is good enough, will update it in next round updating degree [ b ] += 1 q = deque () for i in range ( n ): if degree [ i ] == 1 : q . append ( i ) ans = [] while q : n = len ( q ) ans . clear () for _ in range ( n ): a = q . popleft () ans . append ( a ) for b in g [ a ]: degree [ b ] -= 1 if degree [ b ] == 1 : # final round only 2 left (a,b), then degree[b] here will be 0, and no more node enqueue q . append ( b ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.