Watch 10 video solutions for Minimum Height Trees, a medium level problem involving Depth-First Search, Breadth-First Search, Graph. This walkthrough by NeetCodeIO has 40,652 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |