Minimum Height Trees LeetCode 310 Guide

LeetCode 310 Minimum Height Trees gives you an undirected tree with n nodes labeled 0 to n-1 and n-1 edges. Your goal is to find all nodes that, when chosen as root, result in a tree of minimum possible height. Multiple valid roots may exist, and you must return all of them as a list in any order.

The height of a rooted tree is the number of edges on the longest path from root to any leaf. If you root the same tree at different nodes, the height changes. Nodes near the center of the tree tend to produce shorter trees because they are closer to all other nodes. Nodes near the periphery — the leaves — produce the tallest trees.

The key constraint is that the input is guaranteed to be a tree: it is connected, has no cycles, and has exactly n-1 edges. This makes certain properties reliable — notably that the graph has a well-defined center and diameter, which the solution exploits.

The naive approach tries every node as a root: run BFS or DFS from that node to find the maximum depth, then track the minimum height found across all n starting nodes. This is correct but runs in O(n^2) time — for each of the n nodes you do an O(n) BFS traversal. On a tree with n = 20,000 nodes this is 400 million operations, which is too slow.

The brute force also does a lot of redundant work. When you re-root the tree from node A to its neighbor B, most of the subtree structure stays the same — only the perspective shifts. Re-rooting techniques can exploit this to update the height in O(1) per node, but they are complex to implement correctly under interview pressure.

What we need is a single-pass O(n) algorithm that finds the center(s) directly without trying each root. The leaf trimming approach provides exactly that, using the structural properties of trees.

A leaf node has degree 1 — it connects to exactly one other node. If you root the tree at a leaf, the height is at least n-1 in a path graph, and generally much taller than rooting at a central node. Therefore, leaves can never be the optimal root unless n=1 or n=2. We can safely eliminate all current leaves from consideration.

After removing the first layer of leaves, the remaining nodes form a smaller tree (or forest that quickly reconnects). Some of the remaining nodes now have degree 1 in the reduced graph — they are the new leaves. These new leaves also cannot be optimal roots because the nodes deeper inside are still closer to the overall center. We peel again.

This process of peeling layer by layer from the outside inward is like peeling an onion. Each round of peeling removes the outermost ring of leaves. Eventually, you are left with either 1 node (odd-diameter tree) or 2 adjacent nodes (even-diameter tree). These surviving nodes are exactly the MHT roots.

Initialize a queue with all degree-1 nodes (leaves). Keep a count of remaining nodes, starting at n. Each BFS round, process the entire current queue (one full layer of leaves): for each leaf, remove it from consideration by decrementing the remaining count. For each neighbor of the removed leaf, decrement that neighbor's degree. If the neighbor's degree drops to 1, it is the next round's leaf — add it to the next queue.

The loop continues while remaining nodes > 2. Once only 1 or 2 nodes remain, those are the answer. You never need to do a full BFS from those roots — the trimming process guarantees they are the centers. The trick is processing an entire queue layer at once (like BFS level order) so that all leaves at the same depth are removed simultaneously.

Using sets for the adjacency list (instead of lists) makes neighbor removal trivially O(1). With adjacency sets, when you remove a leaf you can also remove it from its neighbor's set, ensuring degree tracking stays accurate. This is not strictly necessary — the degree array alone is sufficient — but it is a clean implementation choice.

The centers of a tree are defined as the midpoint(s) of its diameter — the longest path between any two nodes. If the diameter has odd length, there is exactly one midpoint node. If the diameter has even length, there are exactly two adjacent midpoint nodes. No tree can have a diameter with more than one midpoint or two adjacent midpoints — this is a fundamental property of paths.

The leaf trimming algorithm converges to these center nodes because it peels from both ends of the diameter simultaneously, closing in on the midpoint(s). Peeling from one side of the diameter advances one step per round, and since both ends shrink symmetrically, the algorithm halts exactly when the center is exposed.

This also explains why the stopping condition is remaining <= 2 rather than remaining == 1. If the tree's diameter is even, the two center nodes are the last two nodes standing. If we waited for just one, we would incorrectly eliminate one of the two valid MHT roots. Always stop at 2.

In Python, build an adjacency list using defaultdict(set) and compute a degree array in a single loop over edges. Initialize a deque with all nodes where degree[i] == 1 (handle n==1 edge case: return [0] immediately). Set remaining = n. While remaining > 2: process all current leaves — for each leaf, remaining -= 1, for each neighbor remove the leaf from its adjacency set and decrement degree; if degree drops to 1, add to next_leaves queue. After the loop, return list of remaining active nodes.

In Java, use ArrayList<Set<Integer>> for the adjacency list and an int[] degree array. Use ArrayDeque<Integer> for the BFS queue. For each edge, add both directions to the adjacency sets and increment both degrees. Seed the queue with all degree-1 nodes. While remaining > 2: process current queue size in a for loop (not while), decrement remaining per leaf, update neighbor degrees, enqueue new leaves. Collect remaining nodes: iterate all n nodes, return those with degree >= 1 or those still in adjacency sets.

Both implementations run in O(n) time and O(n) space. The time bound comes from the fact that each node is added to the leaf queue exactly once and each edge is visited at most twice. Space is O(n) for the adjacency list and degree array. This is optimal — you must read all n nodes and n-1 edges at minimum.

Minimum Height Trees sits at the intersection of tree algorithms and topological-sort-style BFS. The leaf trimming pattern is a specialized technique but the underlying logic — iteratively removing boundary nodes to expose the core — appears in related problems. Course Schedule II (LeetCode 210) applies Kahn's algorithm to find topological ordering; the leaf trimming here is the undirected analogue. Redundant Connection (LeetCode 684) tests whether adding one edge creates a cycle, using Union-Find on tree-like graphs.

The tree diameter concept connects MHT to problems like Binary Tree Diameter (LeetCode 543) and Longest Path in a Tree. Understanding that the MHT roots are the midpoints of the diameter is a transferable insight: any problem asking for the "most central" node(s) in a tree is likely asking about the diameter midpoints.

For a broader foundation, mastering topological sort opens up a large family of graph ordering problems. The pattern — build adjacency structure, identify boundary nodes, peel iteratively — generalizes well. After Minimum Height Trees, study the full topological sort guide to understand how the same boundary-peeling logic handles directed graphs with dependency constraints.