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.Problem Overview: You are given an undirected tree with n nodes labeled from 0 to n-1. Any node can be chosen as the root. The task is to return all nodes that produce a tree with the minimum possible height when used as the root.
Approach 1: Trim the Leaves Iteratively (Topological BFS) (Time: O(n), Space: O(n))
This approach treats the tree like an onion and repeatedly removes outer layers. Start by building an adjacency list and tracking the degree of each node. All nodes with degree 1 are leaves. Push these leaves into a queue and remove them level by level while updating the degree of their neighbors. When a neighbor’s degree becomes 1, it becomes a new leaf and enters the queue. Continue until only one or two nodes remain. Those remaining nodes are the centroids of the tree and represent valid Minimum Height Tree roots. The key insight: the center of a tree remains after peeling away leaves. This process mirrors topological sort applied to an undirected tree and uses a standard breadth-first search queue.
Approach 2: Utilize Two BFS Runs (Tree Diameter Method) (Time: O(n), Space: O(n))
A Minimum Height Tree root must lie at the center of the tree’s diameter. First run BFS from any node (commonly node 0) to find the farthest node A. Then run another BFS from A to find the farthest node B. The path from A to B is the diameter of the tree. The middle node (or two middle nodes if the diameter length is even) forms the Minimum Height Tree roots. During the second BFS, track parent pointers so you can reconstruct the diameter path. This method relies on properties of trees and repeated graph traversal.
Recommended for interviews: The iterative leaf trimming method is the approach most interviewers expect. It directly models the idea of shrinking the tree toward its center and runs in linear time O(n). The two-BFS diameter approach is also optimal and demonstrates strong understanding of tree properties. Showing awareness of both approaches signals strong graph fundamentals.
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.
The C solution describes trimming nodes from the outermost layer (leaves), updating degrees, and reducing the graph until finding potential centroids. This is implemented using arrays to keep track of each node's neighbors and queue for processing leaves.
Time Complexity: O(n), since each node and edge is processed once.
Space Complexity: O(n), for storing edges and nodes’ degrees.
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.
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.
Time Complexity: O(n), for initializing and iterating over nodes.
Space Complexity: O(n), due to graph adjacency representations and queue processing.
If the tree only has one node, then this node is the root of the minimum height tree. We can directly return this node.
If the tree has multiple nodes, there must be leaf nodes. A leaf node is a node that only has one adjacent node. We can use topological sorting to peel off the leaf nodes from the outside to the inside. When we reach the last layer, the remaining nodes are the root nodes of the minimum height tree.
The time complexity is O(n) and the space complexity is O(n), where n is the number of nodes.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Trim the Leaves Iteratively | Time Complexity: O(n), since each node and edge is processed once. |
| Utilize Two BFS Runs | Time Complexity: O(n), for initializing and iterating over nodes. |
| Topological Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Trim the Leaves Iteratively (Topological BFS) | O(n) | O(n) | Best general solution for Minimum Height Trees; commonly expected in interviews |
| Two BFS Runs (Tree Diameter) | O(n) | O(n) | Useful when analyzing tree diameter or when BFS traversal logic is already implemented |
Minimum Height Trees - Leetcode 310 - Python • NeetCodeIO • 40,652 views views
Watch 9 more video solutions →Practice Minimum Height Trees with our built-in code editor and test cases.
Practice on FleetCode