LeetCode 310: Minimum Height Trees ·

Table of Contents

Meta Data
#

Difficulty: medium First Attempt: 2026-04-11 Source: Day 3 learning note

Study Context
#

This article is rebuilt from the exact LeetCode section in the learning note. I kept the note’s repair points, comparison points, and common mistakes, while removing unrelated non-LeetCode material from the same day.

Learning Note Extract
#

LC 310 - Minimum Height Trees
#

Pattern: Topological-style leaf trimming on an undirected tree
Key insight: The root of a minimum height tree must be the center of the tree. A tree has either 1 or 2 centers.
Approach: Build undirected adjacency sets and degree array. Start with all leaves where degree is 1. Remove leaves layer by layer. Each removal reduces neighbor degree. New leaves are added to the queue. Stop when remaining nodes <= 2.
Why leaf trimming works: The farthest nodes from the center are leaves. Removing outer layers repeatedly leaves the center node(s).
Special case: If n == 1, return [0].
Complexity: Time O(n), Space O(n)
Common bugs: Treating this as directed topo sort, forgetting n == 1, returning removed leaves instead of remaining centers, not decrementing remaining node count.

Pattern Comparison
#

Alien Dictionary: Directed graph ordering problem.
Recipes: Directed dependency unlocking problem.
Minimum Height Trees: Undirected tree center problem using topo-style pruning.
Interview distinction: Topological sort is not only one template. The same in-degree idea can model ordering, availability, or layer removal, but the graph direction and meaning must be explained clearly.

Clean Solution
#

The note above captures the reasoning and the mistakes to avoid. The implementation below is the version I would submit.

from collections import deque
from typing import List

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

        graph = [set() for _ in range(n)]
        for a, b in edges:
            graph[a].add(b)
            graph[b].add(a)

        leaves = deque(i for i in range(n) if len(graph[i]) == 1)
        remaining = n
        while remaining > 2:
            size = len(leaves)
            remaining -= size
            for _ in range(size):
                leaf = leaves.popleft()
                nei = graph[leaf].pop()
                graph[nei].remove(leaf)
                if len(graph[nei]) == 1:
                    leaves.append(nei)

        return list(leaves)

Complexity
#

Time O(n), Space O(n).

Mistakes To Watch
#

Trying every root with BFS, causing O(n^2).
Forgetting n=1.

Final Interview Explanation
#

Start from the state definition, then explain why the transition preserves that state. If there is a loop direction, state compression, or a similar-looking problem with a different answer shape, call that out explicitly because that is where this problem family usually breaks down.