Minimum Height Trees
Explanation & Solution
Description
Given a tree of n nodes labeled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [a_i, b_i] indicates an undirected edge between nodes a_i and b_i, find all root labels that minimize the height of the tree. You can choose any node as the root. The height of a rooted tree is the number of edges on the longest downward path from the root to a leaf.
Return a list of all Minimum Height Tree (MHT) root labels. You may return the answer in any order.
Examples
Example 1
Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: When node 1 is chosen as the root, the tree has height 1, which is the minimum possible. Any other root gives a height of 2.
Example 2
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]
Explanation: Both node 3 and node 4 produce trees of height 2, which is the minimum possible.
Constraints
- 1 <= n <= 2 * 10^4
- edges.length == n - 1
- 0 <= a_i, b_i < n
- a_i != b_i
- All pairs (a_i, b_i) are distinct.
- The given input is guaranteed to be a tree.
Approach
Topological Sort pattern
1. Build the Adjacency List
- Create an adjacency list representation of the tree using Sets for efficient deletion.
- For each edge [a, b], add b to adj[a] and a to adj[b].
2. Identify Initial Leaves
- A leaf is any node with exactly one neighbor (degree 1).
- Collect all initial leaves into a list.
3. Iteratively Trim Leaves
- While more than 2 nodes remain:
- Remove all current leaves from the tree.
- For each removed leaf, delete it from its neighbor's adjacency set.
- If a neighbor's degree drops to 1, it becomes a new leaf.
- Replace the leaf list with the new leaves.
4. Return the Remaining Nodes
- When 1 or 2 nodes remain, they are the roots of all Minimum Height Trees.
- Return these nodes as the answer.
Key Insight
- The MHT roots are always the center(s) of the tree — the node(s) that minimize the maximum distance to any other node. A tree has at most 2 centers. By peeling leaves layer by layer (like topological sort), we converge on these centers in O(n) time, analogous to finding the middle of a longest path.
Visualization
Press play to start leaf pruning