← DSA Atlas
Dedicated problem page · #310

Minimum Height Trees

MediumTopological SortTrim leaves inward until the center remainsTopological-style leaf peeling on an undirected tree (multi-source BFS)
Solve on LeetCode ↗
310
MediumTopological SortTopological-style leaf peeling on an undirected tree (multi-source BFS)Trim leaves inward until the center remains

Minimum Height Trees

Given a tree of n nodes labeled 0..n-1 described by n-1 undirected edges, a node can be chosen as root, giving a rooted tree of some height. Return the labels of all roots that minimize the tree's height (there are at most two such roots).

Open official problem prompt ↗
In plain English

Find the tree's center(s): the node or pair of nodes whose greatest distance to any leaf is as small as possible.

Picture it like this

Peeling an onion from the outside in; the last layer you cannot peel without dropping below two nodes is the core.

Example
Input
n = 4, edges = [[1, 0], [1, 2], [1, 3]]
Output
[1]
Why
Rooting at the central node 1 gives height 1; any leaf root gives height 2.
Constraints
1 <= n <= 2 * 10^4edges.length == n - 10 <= a_i, b_i < na_i != b_iThe given edges form a tree (connected, acyclic)
Pattern lesson

See the pattern, then code

Trim leaves inward until the center remains
Recognition clue

You want the most 'central' nodes of a tree to minimize height, and the minimum-height roots are exactly the centroids found by repeatedly stripping outermost leaves.

↗
Topological Sort

Prerequisites, dependencies, build order, or scheduling over a DAG.. The best roots sit in the middle of the tree's longest path. Peeling all current leaves one layer at a time shrinks the tree toward that middle; whatever survives (one or two nodes) are the centroids.

New words, made simpleKnow these before the algorithm
Leaf
A node with exactly one neighbor (degree 1).
Tree center / centroid
The 1 or 2 nodes minimizing eccentricity; the optimal roots here.
Layer peeling
Removing all current leaves simultaneously, like reverse-BFS from the boundary.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
BFS height from every node

Quadratic; too slow at n up to 2*10^4.

Root at each node, BFS to find its height, keep the minima.

Time O(n^2)Space O(n)
Best choiceIterative leaf trimming

Linear and exploits that a tree has at most two centers.

Strip leaf layers until at most two nodes remain; those are the centers.

Time O(n)Space O(n)
The rule we keep true

Invariant

After each peel, the remaining nodes are precisely the centers of the subtree obtained by deleting all removed boundary layers, and the true center is always still inside.

Why this is correct

Reasoning

A tree's center lies at the midpoint of its longest path (diameter). Each peeling round removes exactly the two endpoints of every longest path, shortening the diameter by two, so the process converges on the midpoint(s); an even diameter leaves one center, an odd diameter leaves two.

The algorithm in three movesSay these aloud before coding
1Handle n == 1 separately (the single node is the answer)

leaves = [0, 2, 3], remaining = 4

2Build an undirected adjacency set and collect all leaves (degree 1)

peel layer -> remaining = 1

3Repeatedly remove the whole current leaf layer, updating neighbor degrees and forming the next leaf layer, while more than two nodes remain

surviving = [1]

4Return the 1 or 2 nodes left as the minimum-height-tree roots

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
00
11
22
33
1 · Readedges
2 · AskDegrees?
3 · Update stategraph: 0:{1}, 1:{0,2,3}, 2:{1}, 3:{1}
4 · ResultNode 1 has degree 3.
Key takeaway

Removing leaves 0, 2, 3 leaves the central node 1 as the only root.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Single-node shortcut

    A one-node tree has no edges and no leaves, so answer directly.

  2. 2
    Lines 6-9Undirected adjacency sets

    Sets allow O(1) neighbor removal during trimming.

  3. 3
    Lines 10-11Initial leaf layer

    Degree-1 nodes form the outermost boundary.

  4. 4
    Lines 12-20Peel until <= 2 remain

    Process a full layer per iteration so remaining tracks node count exactly.

  5. 5
    Lines 21Return the center(s)

    The 1 or 2 survivors are the minimum-height roots.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • n == 1 -> [0] with no edges
  • n == 2 -> both nodes are centers, e.g. [0, 1]
  • A path graph -> one or two middle nodes depending on parity
  • A star graph -> the single hub node
!

Common beginner mistakes

  • Peeling one leaf at a time instead of a whole layer, which breaks the remaining count and can return the wrong center
  • Forgetting the n == 1 base case (it has zero leaves, so the loop never runs correctly)
  • Using a list instead of a set for adjacency, making neighbor removal O(degree)
  • Returning up to three or more nodes by looping while remaining > 1 instead of > 2
Check your understanding

Why can there be at most two minimum-height roots?

More in Topological Sort

#207Course ScheduleCycle detection by peeling zero in-degree nodes#210Course Schedule IIEmit nodes in dependency-safe order#269Alien DictionaryDerive edges from adjacent-item comparisons, then topologically sort#329Longest Increasing Path in a MatrixLongest path in an implicit DAG via memoized DFS#1203Sort Items by Groups Respecting DependenciesTwo-level topological sort (order groups, then items within groups)#2050Parallel Courses IIITopological longest path (critical path)