Minimum Height Trees
Last Updated: March 28, 2026
Understanding the Problem
We have a tree with n nodes, and we can pick any node as the root. Different root choices produce different tree heights, and we need to find the root(s) that minimize this height.
The first thing to notice is that a tree always has at most one or two "center" nodes. If you imagine a long path (like a chain), the center is the middle node (or two middle nodes if the path length is even). The same idea generalizes to arbitrary trees: the node(s) that minimize the maximum distance to any other node sit at the tree's center.
So this problem is really asking: find the centroid(s) of the tree. The centroid is the node that minimizes the eccentricity (the maximum distance to any other node). In any tree, there are either one or two centroids, and they are always adjacent if there are two.
The key observation that unlocks the efficient solution: if you keep removing leaf nodes layer by layer (like peeling an onion from the outside), the last remaining node(s) are the centroids. This works because leaves are always the "outermost" nodes, so they can never be MHT roots (unless the tree is trivially small).
Key Constraints:
1 <= n <= 2 * 10^4--> With up to 20,000 nodes, O(n^2) is around 4 * 10^8 operations. That is borderline and likely too slow. We should aim for O(n).edges.length == n - 1--> This confirms the input is a tree (connected, n-1 edges). No cycles to worry about.- The input is guaranteed to be a tree --> No need to validate connectivity or check for cycles.
Approach 1: Brute Force (BFS from Every Node)
Intuition
The most direct approach: try every node as the root, compute the tree height using BFS (or DFS), and keep track of which root(s) produce the minimum height.
For any given root, the tree height is the longest path from that root to any leaf. BFS naturally computes this since the depth of the last level visited equals the tree height. So we run BFS from every node, record the height, find the minimum, and collect all nodes that achieve it.
This is the brute force because we are doing n separate BFS traversals, each taking O(n) time.
Algorithm
- Build an adjacency list from the edges.
- For each node
ifrom 0 to n-1:
a. Run BFS starting from node i.
b. Record the maximum depth reached (this is the tree height when rooted at i).
- Find the minimum height across all nodes.
- Return all nodes whose height equals the minimum.
Example Walkthrough
Input:
BFS from node 0: height = 2. BFS from node 1: height = 1. BFS from node 2: height = 2. BFS from node 3: height = 2. Minimum height = 1, achieved by node 1.
Code
- Time Complexity: O(n^2). We run BFS from each of the n nodes, and each BFS visits all n nodes and n-1 edges, taking O(n) time. Total: O(n * n) = O(n^2).
- Space Complexity: O(n). The adjacency list takes O(n) space. Each BFS uses O(n) for the visited array and queue.
The bottleneck is running a full BFS from every single node. We do not actually need to know the height for every root. We just need to find the center of the tree. What if instead of measuring from every root, we worked inward from the outside?
Approach 2: Topological Leaf Trimming (Optimal)
Intuition
A leaf node (a node with degree 1) can never be an MHT root, unless the tree has only 1 or 2 nodes. A leaf is at the periphery of the tree. If you root the tree at a leaf, the entire rest of the tree hangs below it, creating a tall chain. You would always get a shorter tree by moving the root toward the center.
So we can safely eliminate all leaves. But once we remove the current leaves, some of their neighbors become the new leaves of the smaller tree. We can remove those too. If we keep going, peeling away layer after layer of leaves, eventually we are left with just 1 or 2 nodes. Those are the centroids of the tree, and they are our MHT roots.
This is essentially topological sort on a tree. Think of it like BFS-based Kahn's algorithm, but instead of removing nodes with in-degree 0 in a DAG, we remove nodes with degree 1 in an undirected tree. Each round removes one "layer" of outermost nodes, and the process converges to the center.
The correctness hinges on two facts about trees. First, a leaf can never be a centroid (for n >= 3). If you root the tree at a leaf L, the height is the longest path starting from L. But L has only one neighbor, so the entire tree hangs below that neighbor. Moving the root from L to its neighbor can only reduce the height.
Second, removing all leaves simultaneously preserves the center. After one round of leaf removal, the remaining tree is a smaller tree with the same center. This is because the center is defined by maximum distance to any node, and all leaves are equally "outermost." Removing them all at once shrinks every longest path by exactly 1 from each end.
So each round peels one layer from the outside, and after enough rounds, only the center remains. Since a tree's center has at most 2 nodes, we stop when 2 or fewer remain.
Algorithm
- Handle edge cases: if
n == 1, return[0]. Ifn == 2, return[0, 1]. - Build an adjacency list and compute the degree of each node.
- Collect all initial leaves (nodes with degree 1) into a queue.
- While the number of remaining nodes is greater than 2:
a. For each leaf in the current queue, "remove" it by decrementing the degree of its neighbor.
b. Subtract the number of removed leaves from the remaining count.
c. If any neighbor's degree drops to 1, it becomes a new leaf. Add it to the next queue.
d. Replace the current queue with the next queue.
- Return the remaining nodes (the last set of leaves).
Example Walkthrough
Code
- Time Complexity: O(n). Building the adjacency list takes O(n) since there are n-1 edges. Each node is added to the leaf queue exactly once and removed exactly once. Each edge is processed at most twice. Total work: O(n).
- Space Complexity: O(n). The adjacency list stores 2 * (n-1) entries. The degree array and the leaf queue each take O(n) space.