#310 Minimum Height Trees

frequently reported atGoogle Amazon Microsoft

the problem

In plain words

Given a tree of n nodes (n − 1 undirected edges), choosing any node as the root gives some height. Return all roots that give the minimum height (in any order).

in n = 4, edges = [[1,0],[1,2],[1,3]]

out [1]

in n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]

out [3,4]

1 ≤ n ≤ 2·10⁴
edges.length == n − 1
The input is a tree

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTopological sort & cycle detection Multi-source BFS

The best roots are the centres of the longest path. Peel off all leaves at once, layer by layer, until 1 or 2 nodes remain — they are the answer.

solutions

From brute force to optimal

Compute the height for every possible root, keep the minimum.

For each root, BFS to find the farthest distance.
Keep all roots with the smallest height.

timeO(n²)

n BFS runs of O(n) each — 4·10⁸ steps at the limit: too slow.

spaceO(n)

Adjacency list and one distance array.

javajava.util.*

1class Solution {2    public List<Integer> findMinHeightTrees(int n, int[][] edges) {3        List<List<Integer>> adj = new ArrayList<>();4        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());5        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }6        int best = Integer.MAX_VALUE;7        List<Integer> roots = new ArrayList<>();8        for (int r = 0; r < n; r++) {9            int h = height(r, adj, n);10            if (h < best) { best = h; roots.clear(); }11            if (h == best) roots.add(r);12        }13        return roots;14    }15 16    private int height(int root, List<List<Integer>> adj, int n) {17        int[] dist = new int[n];18        Arrays.fill(dist, -1);19        Deque<Integer> queue = new ArrayDeque<>();20        queue.offer(root);21        dist[root] = 0;22        int max = 0;23        while (!queue.isEmpty()) {24            int u = queue.poll();25            max = Math.max(max, dist[u]);26            for (int v : adj.get(u)) if (dist[v] == -1) { dist[v] = dist[u] + 1; queue.offer(v); }27        }28        return max;29    }30}

Kahn's algorithm on degrees: leaves (degree 1) are removed in rounds; the last 1–2 nodes are the centres.

n == 1 → [0].
Queue every degree-1 node.
While more than 2 nodes remain, remove a whole layer of leaves and enqueue neighbours that become leaves.
Return what's left in the queue.

timeO(n)

Each node is removed once, each edge decremented twice.

spaceO(n)

Adjacency list, degrees and the queue.

javajava.util.*

1class Solution {2    public List<Integer> findMinHeightTrees(int n, int[][] edges) {3        if (n == 1) return List.of(0);4        List<List<Integer>> adj = new ArrayList<>();5        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());6        int[] degree = new int[n];7        for (int[] e : edges) {8            adj.get(e[0]).add(e[1]);9            adj.get(e[1]).add(e[0]);10            degree[e[0]]++;11            degree[e[1]]++;12        }13        Deque<Integer> leaves = new ArrayDeque<>();14        for (int v = 0; v < n; v++) {15            if (degree[v] == 1) leaves.offer(v);16        }17        int remaining = n;18        while (remaining > 2) {19            int size = leaves.size();20            remaining -= size;21            for (int k = 0; k < size; k++) {22                int leaf = leaves.poll();23                for (int nb : adj.get(leaf)) {24                    degree[nb]--;25                    if (degree[nb] == 1) leaves.offer(nb);26                }27            }28        }29        return new ArrayList<>(leaves); // the 1 or 2 centres30    }31}

sim

Peel the leaves

loading simulation…

javajava.util.*

1class Solution {2    public List<Integer> findMinHeightTrees(int n, int[][] edges) {3        if (n == 1) return List.of(0);4        List<List<Integer>> adj = new ArrayList<>();5        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());6        int[] degree = new int[n];7        for (int[] e : edges) {8            adj.get(e[0]).add(e[1]);9            adj.get(e[1]).add(e[0]);10            degree[e[0]]++;11            degree[e[1]]++;12        }13        Deque<Integer> leaves = new ArrayDeque<>();14        for (int v = 0; v < n; v++) {15            if (degree[v] == 1) leaves.offer(v);16        }17        int remaining = n;18        while (remaining > 2) {19            int size = leaves.size();20            remaining -= size;21            for (int k = 0; k < size; k++) {22                int leaf = leaves.poll();23                for (int nb : adj.get(leaf)) {24                    degree[nb]--;25                    if (degree[nb] == 1) leaves.offer(nb);26                }27            }28        }29        return new ArrayList<>(leaves); // the 1 or 2 centres30    }31}

in the room

How to say it in the interview

talk track

Claim: at most 2 answers, because a path's middle is one node or two adjacent nodes.
Explain peeling: each round shortens every longest path by one at both ends, so the middle survives last.

traps

Stopping at remaining > 1 — with 2 centres you'd peel both away. Stop at remaining ≤ 2.
Forgetting n == 1 (no leaves of degree 1).

what they ask next

Follow-ups

Alternative?

BFS twice to find the diameter path (farthest from any node, then farthest from that), and take its middle 1–2 nodes — also O(n).

before you submit

Edge cases to test

n = 1 → [0] (no edges, so no degree-1 leaves).
n = 2 → [0, 1].
A path with an even number of nodes has 2 centres; an odd one has 1.

practise next