Minimum Height Trees: Topological Trimming to Find the Center

May 18, 20265 min read

leetcodeproblemmediumtreesgraph

LeetCode 310. Minimum Height Trees gives you n nodes labeled 0 to n-1 and a list of undirected edges that form a tree. Your task is to find all roots that produce the minimum possible tree height. A tree's height is the longest path from the root to any leaf.

The answer is not obvious at first. If you pick a node at the periphery of the tree as the root, all the other nodes sprawl outward and the height is large. If you pick a node near the center, the tree stays compact and the height shrinks.

Graph with n=6. Nodes 0, 1, 2, and 5 are leaves (degree 1, red). Nodes 3 and 4 are the centers that minimize tree height (green).

The key insight

No matter what the tree looks like, the answer is always 1 or 2 nodes. These nodes sit at the center of the longest path in the tree. From any center node, the farthest leaf is as close as possible, so the resulting tree height is minimized.

The algorithm that finds them is elegant: repeatedly peel off leaf nodes (nodes with degree 1) layer by layer, like peeling an onion, until 1 or 2 nodes remain. Those survivors are the MHT roots.

Why does this work? Leaf nodes can never be good roots, because choosing one as the root forces every other node to hang beneath it, maximizing height. You can always do better by moving the root one step inward. By trimming leaves in rounds, you converge on the center from all directions at once.

The solution

from collections import deque

def findMinHeightTrees(n: int, edges: list[list[int]]) -> list[int]:
    if n == 1:
        return [0]
    adj = [set() for _ in range(n)]
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)
    leaves = deque(i for i in range(n) if len(adj[i]) == 1)
    remaining = n
    while remaining > 2:
        leaf_count = len(leaves)
        remaining -= leaf_count
        for _ in range(leaf_count):
            leaf = leaves.popleft()
            neighbor = next(iter(adj[leaf]))
            adj[neighbor].remove(leaf)
            if len(adj[neighbor]) == 1:
                leaves.append(neighbor)
    return list(leaves)

A few things to notice:

You handle n == 1 separately because a single node has no edges and adj would have no leaves to seed the queue.
You use remaining to track how many nodes are still active. The loop stops when 2 or fewer remain, not when the queue is empty.
Each round, you process exactly the current batch of leaves. After removing them, their neighbors may become the new leaves, so you check and enqueue them immediately.
The adjacency structure is sets, not lists, so removal of a specific neighbor is O(1) on average.

Practice graph trimming problems

Step-by-step walkthrough

Here is the algorithm traced on the 6-node graph from above, with edges [[1,0],[1,2],[1,3],[3,4],[4,5]] (same tree, different notation). Nodes 0, 2, and 5 are leaves; node 1 connects to node 3 which connects to node 4.

Initial state: identify all leaf nodes (degree = 1)

Leaves: {0, 1, 2, 5}

Nodes 0, 1, 2, and 5 each have exactly one neighbor. They are the current leaves.

Round 1: trim all leaves — remaining nodes = 6 - 4 = 2, stop

Leaves: {3, 4}

After removing the four leaves, nodes 3 and 4 each have degree 1. Remaining count is 2, so we stop. These are the MHT roots.

After one round of trimming, exactly 2 nodes remain. The loop exits and returns them as the answer. No second round is needed here, but for larger trees you may need several rounds before you converge.

Drill this pattern with spaced repetition

Complexity analysis

Dimension	Bound	Reason
Time	O(n)	Each node and edge is processed at most once
Space	O(n)	Adjacency sets and the leaf queue each hold at most n entries

The O(n) time bound is the same as for topological sort on a DAG. You visit every node once when it becomes a leaf, and you touch every edge twice (once from each endpoint). The total work is proportional to n plus the number of edges, and a tree has exactly n minus 1 edges, so both are O(n).

Building blocks

Topological sort and leaf peeling

The leaf-trimming loop is essentially topological sort applied to an undirected tree. In topological sort on a directed graph, you process nodes whose in-degree has dropped to zero. Here you process nodes whose degree has dropped to 1. The structure is the same: maintain a queue of "ready" nodes, process them one batch at a time, and update neighbors.

The reason you stop at 2 nodes instead of 0 is that undirected trees have no directed "sink." The last two nodes would each point to the other, and neither would ever reach degree 0. Stopping at 2 is the undirected analog of stopping when the queue is empty.

Degree-based graph reasoning

Degree is a surprisingly powerful tool for graph problems. When you know a node's degree, you immediately know something about its role in the graph. Degree 1 means a leaf, and leaves are never optimal roots. Degree 2 means an internal node on a path with no branching. High degree means a hub that connects many subtrees.

Maintaining degrees dynamically as you remove nodes is a pattern that shows up in topological sort (in-degree), Kahn's algorithm, and this problem. Every time you remove a node, you decrement its neighbors' degrees and check whether any have crossed a threshold.

Edge cases

n = 1. The graph has one node and no edges. The only possible root is 0, and the tree height is 0. Handle this before building the adjacency list, since there are no leaves to seed the queue.
n = 2. Both nodes are leaves. The tree is a single edge, and either node is a valid root producing height 1. The loop condition remaining > 2 immediately exits and returns both.
Linear chain. For a path graph like 0-1-2-3-4, each trimming round removes one node from each end. After two rounds you have node 2 remaining alone. The answer is [2], the single center of the path.

From understanding to recall

The leaf-trimming insight is not something you derive from first principles in 5 minutes under pressure. Once you see it, it feels obvious. But to produce it reliably in an interview, you need to have seen the pattern enough times that it surfaces automatically.

That is where spaced repetition changes the game. Reviewing this problem once and moving on means you will forget the key insight (the center observation) and remember only the vague shape. Reviewing it at increasing intervals, each time reconstructing the reasoning from scratch, builds the kind of recall that holds up when you are nervous and the clock is running.

The pattern to drill: degree-1 nodes are useless as roots. Trim them. Their neighbors may become the new degree-1 nodes. Trim those too. Stop at 2. That is the whole algorithm in four sentences.

Course Schedule - Cycle detection using DFS on a directed graph
Course Schedule II - Topological ordering with Kahn's algorithm
Clone Graph - Building adjacency structures and traversing undirected graphs

Try CodeBricks free