LeetCode · #310

Minimum Height Trees Solution

Given an undirected tree, return all root labels that produce the minimum possible tree height.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #310

🏗️

Pattern

Leaf trimming / degree peeling

A tree with n nodes has exactly n - 1 edges and no cycles. If you choose any node as the root, the tree gets some height. Return every node whose rooted height is minimum.

Example

Input:  n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
// Rooting at 1 gives height 1, which is minimum.

Constraints

• 1 ≤ n ≤ 20000
• edges.length == n - 1
• The input graph is a tree

Section Two · Approach 1

Try Every Root with BFS — O(n²)

For every node, run BFS to measure the farthest distance to any other node. That farthest distance is the tree height when rooted there. Track the minimum height and collect all nodes achieving it.

Why it works

BFS from a fixed root visits nodes level by level, so the deepest level reached is the height of the rooted tree.

Problem: A BFS from every node is too expensive for n = 20000. Trees have special structure we can exploit: the optimal roots are the center or two centers of the tree diameter. Repeatedly peeling off leaves finds those centers directly.

Section Three · Approach 2

Trim Leaves Layer by Layer — O(V + E)

Initialize all leaves (degree 1) in a queue. Remove the current leaf layer, decrement neighbors' degrees, and any neighbor that becomes degree 1 is a new leaf. Continue until at most 2 nodes remain. Those remaining nodes are the MHT roots.

💡 Mental model: Imagine burning a tree from the outside inward. The leaves burn first. Then new leaves are exposed and burn next. The last one or two nodes left unburned are the center(s), which are exactly the roots that minimize height.

If n == 1, the answer is [0].
Build an undirected adjacency list and degree array.
Seed queue with all degree-1 nodes.
Process leaves one layer at a time, subtracting them from remainingNodes.
When remainingNodes ≤ 2, the queue holds the answer.

Why this belongs near topological sort:

It uses the same degree-peeling idea as Kahn's algorithm, but on an undirected tree.
Instead of removing indegree-0 nodes, we remove degree-1 leaves until the center remains.

Section Four · Trace

Visual Walkthrough

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

Minimum Height Trees — leaf trimming

Section Five · Implementation

Code — Java & Python

Java — degree peeling

import java.util.*;

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Collections.singletonList(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[] edge : edges) {
            int u = edge[0], v = edge[1];
            adj.get(u).add(v);
            adj.get(v).add(u);
            degree[u]++;
            degree[v]++;
        }

        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) queue.offer(i);
        }

        int remaining = n;
        while (remaining > 2) {
            int size = queue.size();
            remaining -= size;
            for (int i = 0; i < size; i++) {
                int leaf = queue.poll();
                for (int nei : adj.get(leaf)) {
                    if (--degree[nei] == 1) queue.offer(nei);
                }
            }
        }

        return new ArrayList<>(queue);
    }
}

Python — trim outer leaves

from collections import deque

class Solution:
    def findMinHeightTrees(self, n: int, edges: list[list[int]]) -> list[int]:
        if n == 1:
            return [0]

        adj = [[] for _ in range(n)]
        degree = [0] * n

        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
            degree[u] += 1
            degree[v] += 1

        queue = deque(i for i in range(n) if degree[i] == 1)
        remaining = n

        while remaining > 2:
            size = len(queue)
            remaining -= size
            for _ in range(size):
                leaf = queue.popleft()
                for nei in adj[leaf]:
                    degree[nei] -= 1
                    if degree[nei] == 1:
                        queue.append(nei)

        return list(queue)

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
BFS from every root	O(n²)	O(n)	Too slow for large trees.
Leaf trimming ← optimal	O(V + E)	O(V + E)	Each node enters the queue at most once; each edge is processed a constant number of times.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Expected behavior	Why it matters
`n = 1`	Return `[0]`	The single node is trivially the only center.
Two-node tree	Return both nodes	Both are valid centers; stopping condition is ≤ 2 nodes.
Star graph	Return the hub	All leaves peel away in one round.
Path graph	Return one or two middle nodes	Tree centers lie in the middle of the diameter.
Stopping too late	Wrong answer	Stop when remaining nodes are ≤ 2, not when the queue becomes empty.

⚠ Common Mistake: Treating this like a normal topological sort and processing until the queue is empty. If you remove the final one or two centers as well, you lose the answer. The centers are the last nodes remaining, so stop as soon as remaining ≤ 2.

← Back to Topological Sort

LearningTree

LC 310 · Minimum Height Trees — Solution & Explanation | DSA Guide