Problem 24.6 · Topological SortMedium

Minimum Height Trees

What it teaches: Kahn's idea on an undirected tree: peel leaves layer by layer until the centre remains.

Practise it on judges as “Minimum Height Trees”.

The problem

Given a tree with n nodes, return all roots that give the minimum height (in any order). There are at most two.

Example 1

Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3, 4]

Constraints

1 ≤ n ≤ 2 × 10⁴

Pattern clues in the wording

→ Centre of a tree
→ Minimise the maximum distance

These clues point to Topological Sort: Order the nodes of a directed graph so every edge goes from earlier to later, by repeatedly taking nodes with no remaining prerequisites.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

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

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 4 edges = [[1,0],[1,2],[1,3]]	[1]
2	n = 6 edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]	[3,4]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Leaf trimming · O(n)

Leaf trimming

Time O(n) Space O(n)

Degrees; queue all leaves (degree 1). While more than 2 nodes remain, remove the current leaves and collect neighbours whose degree drops to 1 as the next layer.

Approach 1

import java.util.*;

class Solution {
    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[] deg = new int[n];
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); deg[e[0]]++; deg[e[1]]++; }
        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; i++) if (deg[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 (--deg[v] == 1) next.add(v);
            leaves = next;
        }
        return leaves;
    }
}

Verdict: Linear; BFS from every node would be O(n²).

Before you submit

Edge cases and common mistakes

Test these inputs

n = 1
n = 2 (both nodes)
A path (one or two middle nodes)

Mistakes people make

Stopping when one node remains instead of ≤ 2 (two centres are possible).

Interview

Follow-up questions

Another way to find the centre?

Command Palette

The problem

Approaches

Leaf trimming

Edge cases and common mistakes

Follow-up questions