Minimum Height Trees

MediumGraphs · Topological Sort (Leaf Trimming)🧩 Topological Sort LeetCode #310 ↗Updated Oct 30, 2026

Problem

You are given an undirected tree with n nodes labelled 0..n-1 as a list of n-1 edges. Hanging the tree from any node gives a rooted tree whose height is the number of edges on its longest root-to-leaf path. Return every node that, used as the root, gives the smallest possible height (any order).

Inputn = 5, edges = [[0,1],[1,2],[2,3],[2,4]]Output[1,2]

Inputn = 4, edges = [[0,3],[1,3],[2,3]]Output[3]

Inputn = 1, edges = []Output[0]

1 ≤ n ≤ 2·10⁴ · edges.length = n - 1 · the input is guaranteed to be a tree

Try it yourself

Java

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The best roots are the centre of the tree's longest path, so there are only one or two of them. Peel off all current leaves layer by layer (like Kahn's algorithm on degree 1) — the last 1 or 2 nodes standing are the centres.

PatternTopological Sort

Instinct Tasks with prerequisites, "X must come before Y", or an order hidden in comparisons: build a directed graph and peel off nodes with zero in-degree.

Memory hack No prereqs? Off you go. Each finished task frees its followers; if someone is never freed, there is a cycle.

Open the Topological Sort guide →

Approaches

Brute ForceBFS Height From Every Root

Time O(n²)Space O(n)

Try every node as the root: a BFS gives the number of levels, i.e. the height. Keep the nodes that achieve the minimum height seen so far.

Java

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    int best = Integer.MAX_VALUE;
    List<Integer> roots = new ArrayList<>();
    for (int r = 0; r < n; r++) {
        int h = height(adj, r, n);
        if (h < best) {
            best = h;
            roots.clear();
        }
        if (h == best) roots.add(r);
    }
    return roots;
}

private int height(List<List<Integer>> adj, int root, int n) {
    boolean[] seen = new boolean[n];
    Deque<Integer> queue = new ArrayDeque<>();
    queue.add(root);
    seen[root] = true;
    int levels = -1;
    while (!queue.isEmpty()) {
        levels++;
        for (int size = queue.size(); size > 0; size--) {
            int u = queue.poll();
            for (int v : adj.get(u)) {
                if (!seen[v]) {
                    seen[v] = true;
                    queue.add(v);
                }
            }
        }
    }
    return levels;
}

Direct translation of the definition; too slow at n = 2·10⁴.

BetterMiddle of the Diameter (Two BFS)

Time O(n)Space O(n)

The height from any root is at least half the tree's longest path (diameter), and the middle of that path achieves it. BFS from any node finds one diameter end a; BFS from a with parent links finds the other end b. Walk back from b and return the middle 1 or 2 nodes.

Java

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    int[] parent = new int[n];
    int a = farthest(adj, 0, parent);
    int b = farthest(adj, a, parent);
    List<Integer> path = new ArrayList<>(); // b ... a
    for (int v = b; v != -1; v = parent[v]) path.add(v);
    int len = path.size();
    if (len % 2 == 1) return List.of(path.get(len / 2));
    return List.of(path.get(len / 2 - 1), path.get(len / 2));
}

// BFS from src; fills parent[] and returns the last (farthest) node reached.
private int farthest(List<List<Integer>> adj, int src, int[] parent) {
    Arrays.fill(parent, -2);
    parent[src] = -1;
    Deque<Integer> queue = new ArrayDeque<>();
    queue.add(src);
    int last = src;
    while (!queue.isEmpty()) {
        last = queue.poll();
        for (int v : adj.get(last)) {
            if (parent[v] == -2) {
                parent[v] = last;
                queue.add(v);
            }
        }
    }
    return last;
}

Linear, but needs a proof about diameters plus path reconstruction.

OptimalLeaf Trimming (Topological Peeling)

Time O(n)Space O(n)

Leaves are never optimal roots (their neighbour is always at least as good). Remove all current leaves at once, decrement their neighbours' degrees, and queue neighbours that become leaves. Each round shrinks every longest path by 2 from both ends, so when at most 2 nodes remain they are the centre.

Java

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    if (n == 1) return List.of(0);
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    int[] degree = new int[n];
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
        degree[e[0]]++;
        degree[e[1]]++;
    }
    List<Integer> leaves = new ArrayList<>();
    for (int i = 0; i < n; i++) if (degree[i] == 1) leaves.add(i);
    int remaining = n;
    while (remaining > 2) {
        remaining -= leaves.size();
        List<Integer> next = new ArrayList<>();
        for (int leaf : leaves) {
            for (int v : adj.get(leaf)) {
                if (--degree[v] == 1) next.add(v); // v just became a leaf
            }
        }
        leaves = next;
    }
    return leaves;
}

Linear, iterative and needs no path bookkeeping — the standard answer.

Pro tip

Loop while remaining > 2, not until the queue is empty — otherwise you trim the centres too.

At a glance

Level	Approach	Time	Space
Brute Force	BFS Height From Every Root	`O(n²)`	`O(n)`
Better	Middle of the Diameter (Two BFS)	`O(n)`	`O(n)`
Optimal	Leaf Trimming (Topological Peeling)	`O(n)`	`O(n)`

Common pitfalls

Forgetting n == 1 (no edges, no leaves) — the answer is [0].
Trimming one leaf at a time instead of a whole layer — you lose track of the centre.
Assuming a single answer — an even-length diameter has two centres.

Interview tips

Start from the definition (BFS per root) to show you understand height.
Claim and justify: at most 2 roots, and they are the middle of the diameter.
Draw a path graph and peel leaves — it makes the trimming argument obvious.

Pattern

Leaf trimming / topological peeling → find the centre(s) of a tree or strip away everything that is not on a core structure.

My notes saved in this browser