Minimum Height Trees

Problem Description

A tree is an undirected graph in which any two vertices are connected by exactly one path. Given a tree of n nodes labeled from 0 to n - 1, and an array of n - 1 edges, return a list of all minimum height trees (MHTs) root labels. The answer can be returned in any order.

Examples

Constraints

• 1 ≤ n ≤ 2 * 10⁴
• edges.length == n - 1
• 0 ≤ ai, bi < n
• ai != bi
• All pairs (ai, bi) are distinct

Peel the Onion: Remove Leaves Layer by Layer

The MHT root is the center of the tree. A tree can have at most 2 centers (for even-length longest paths, both midpoints qualify).

Think of it like peeling an onion: repeatedly remove all current leaf nodes (degree 1). The remaining nodes, after peeling can’t reduce further, are the centers. This is topological sort applied to a tree.

Stop when 1 or 2 nodes remain. Those are the MHT roots.

Solution: Iterative Leaf Pruning (BFS-style)

import java.util.*;

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return List.of(0);

        List<Set<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new HashSet<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }

        // find initial leaves
        Queue<Integer> leaves = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (adj.get(i).size() == 1) leaves.offer(i);
        }

        int remaining = n;
        while (remaining > 2) {
            int leafCount = leaves.size();
            remaining -= leafCount;
            for (int i = 0; i < leafCount; i++) {
                int leaf = leaves.poll();
                int neighbor = adj.get(leaf).iterator().next();
                adj.get(neighbor).remove(leaf);
                if (adj.get(neighbor).size() == 1) {
                    leaves.offer(neighbor);
                }
            }
        }

        return new ArrayList<>(leaves);
    }
}

from collections import deque

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

        adj = [set() for _ in range(n)]
        for u, v in edges:
            adj[u].add(v)
            adj[v].add(u)

        leaves = deque(i for i in range(n) if len(adj[i]) == 1)
        remaining = n

        while remaining > 2:
            leaf_count = len(leaves)
            remaining -= leaf_count
            for _ in range(leaf_count):
                leaf = leaves.popleft()
                neighbor = next(iter(adj[leaf]))
                adj[neighbor].discard(leaf)
                if len(adj[neighbor]) == 1:
                    leaves.append(neighbor)

        return list(leaves)

#include <vector>
#include <queue>
#include <unordered_set>

class Solution {
public:
    std::vector<int> findMinHeightTrees(int n, std::vector<std::vector<int>>& edges) {
        if (n == 1) return {0};

        std::vector<std::unordered_set<int>> adj(n);
        for (auto& e : edges) { adj[e[0]].insert(e[1]); adj[e[1]].insert(e[0]); }

        std::queue<int> leaves;
        for (int i = 0; i < n; i++) if (adj[i].size() == 1) leaves.push(i);

        int remaining = n;
        while (remaining > 2) {
            int sz = leaves.size();
            remaining -= sz;
            while (sz--) {
                int leaf = leaves.front(); leaves.pop();
                int neighbor = *adj[leaf].begin();
                adj[neighbor].erase(leaf);
                if (adj[neighbor].size() == 1) leaves.push(neighbor);
            }
        }

        std::vector<int> result;
        while (!leaves.empty()) { result.push_back(leaves.front()); leaves.pop(); }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n). Each node is added to the leaves queue at most once. Removing it from its neighbor’s adjacency set is O(1) average for hash sets.
• Space Complexity: O(n) for the adjacency list.

Where it breaks: the loop condition is remaining > 2, not remaining > 1. A tree can have exactly 2 MHT roots (when the diameter is even), and stopping at 2 gives both. Stopping at 1 would miss one valid root.

Common Mistakes

• Not handling n == 1 separately. A single node has no edges, so the leaf-detection loop finds nothing and returns an empty list. Handle explicitly.
• Using a list instead of a set for the adjacency. When you remove a leaf from its neighbor’s adjacency, you need O(1) removal. An adjacency list with O(n) removal makes the algorithm O(n²).
• Stopping at remaining > 1 instead of remaining > 2. You miss the case where two nodes tie for the center.

← All Problems