Minimum Height Trees
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.
A tree always has at most one or two center nodes. In a simple path, the center is the middle node, or the two middle nodes when the path has an even number of edges. The same idea generalizes to any tree: the node or nodes that minimize the maximum distance to any other node sit at the tree's center.
So the problem reduces to finding the centroid(s) of the tree. A centroid minimizes the eccentricity, which is the maximum distance from that node to any other node. A tree has one or two centroids, and when there are two, they are adjacent.
This leads to an efficient solution. If we repeatedly remove the leaf nodes layer by layer, the last remaining node or pair of nodes are the centroids. Leaves are the outermost nodes, so they cannot be MHT roots unless the tree has only one or two nodes.
Key Constraints:
1 <= n <= 2 * 10^4--> With up to 20,000 nodes, an O(n^2) solution runs around 4 * 10^8 operations, which is too slow. We need O(n).edges.length == n - 1and the input is guaranteed to be a tree --> The graph is connected with no cycles, so we never have to validate connectivity or detect cycles.
Approach 1: Brute Force (BFS from Every Node)
Intuition
Try every node as the root, compute the tree height with BFS, and track which root or roots produce the minimum height.
For a given root, the tree height is the longest path from that root to any leaf. A level-order BFS computes this directly: the depth of the last level visited equals the height. We run BFS from every node, record the height, find the minimum, and collect every node that achieves it.
This costs n separate BFS traversals, each O(n) time.
Algorithm
- Build an adjacency list from the edges.
- For each node
ifrom 0 to n-1: - Run BFS starting from node
i. - 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:
Node 1 is connected to 0, 2, and 3. The other three nodes are leaves hanging off node 1.
BFS from node 0: visit 0 (depth 0), then 1 (depth 1), then 2 and 3 (depth 2). Height = 2.
BFS from node 1: visit 1 (depth 0), then 0, 2, 3 (depth 1). Height = 1.
BFS from node 2: same shape as node 0. Height = 2.
BFS from node 3: same shape as node 0. Height = 2.
Heights array = [2, 1, 2, 2]. Minimum = 1, achieved only by node 1. Result = [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 node. We do not need the height for every root, only the center of the tree. The next approach finds the center directly by working inward from the leaves.
Approach 2: Topological Leaf Trimming (Optimal)
Intuition
A leaf node (degree 1) can never be an MHT root unless the tree has only 1 or 2 nodes. A leaf sits at the periphery. Rooting the tree at a leaf forces the rest of the tree to hang below it as a long chain, and moving the root to the leaf's neighbor reduces the height. So leaves are never centers.
Once the current leaves are removed, some of their neighbors become the leaves of the smaller tree, and we remove those too. Repeating this leaf removal layer by layer leaves 1 or 2 nodes, which are the centroids and the MHT roots.
This is topological sort on a tree, structured like Kahn's algorithm. Instead of removing in-degree 0 nodes from a DAG, we remove degree 1 nodes from an undirected tree. Each round strips one layer of outermost nodes, converging on the center.
The argument rests on two facts about trees. First, for n >= 3, a leaf cannot be a centroid. Rooting at a leaf L gives a height equal to the longest path from L, but L has a single neighbor, so the whole tree hangs below that neighbor. Moving the root from L to that neighbor cannot increase the height and usually decreases it.
Second, removing all current leaves at once preserves the center. Every longest path in the tree ends at a leaf on both ends, so deleting all leaves shortens every longest path by exactly 1 at each end. The midpoint of those paths, which is the center, does not move. The remaining graph is a smaller tree with the same center.
Each round therefore removes one outer layer without disturbing the center. After enough rounds only the center remains, and since a tree has at most 2 centers, we stop once 2 or fewer nodes are left.
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:
- For each leaf in the current queue, "remove" it by decrementing the degree of its neighbor.
- Subtract the number of removed leaves from the remaining count.
- If any neighbor's degree drops to 1, it becomes a new leaf. Add it to the next queue.
- 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.