Minimum Height Trees Solution

Problem

Given an undirected tree with n nodes (labeled 0 to n-1) and n-1 edges, you can choose any node as the root. Different root choices produce different tree heights — find every root that results in the minimum possible height, and return them in any order.

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: node 1 connects directly to all others, so rooting there gives height 1; any leaf root requires 2 hops to reach the far side.

Counter-example: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] → [3,4]. Both nodes 3 and 4 achieve height 2; all other roots reach height 3 or more.

Intuition

The minimum-height roots are always the center(s) of the tree's longest path — there are at most two of them. Imagine peeling the tree like an onion: strip all current leaf nodes, expose the next layer, and repeat. The last 1 or 2 nodes left standing are exactly those centers.

Approach 1 — Brute Force BFS

Try every node as a candidate root, measure the resulting height with BFS, and keep track of the minimum.

Build an adjacency list from the edge list.
For each node, run a level-by-level BFS from that node and count the number of levels — that is the height.
If the new height is smaller than the current minimum, reset the result list; if it ties, append.
Return the collected roots after all n BFS passes.

1from collections import deque
2from typing import List
3
4def findMinHeightTrees(n: int, edges: List[List[int]]) -> List[int]:
5    if n == 1:
6        return [0]
7
8    adj = [[] for _ in range(n)]
9    for u, v in edges:
10        adj[u].append(v)
11        adj[v].append(u)
12
13    def bfs_height(root: int) -> int:
14        visited = {root}
15        queue = deque([root])
16        height = -1
17        while queue:
18            height += 1
19            for _ in range(len(queue)):  # drain one BFS level per iteration
20                node = queue.popleft()
21                for neighbor in adj[node]:
22                    if neighbor not in visited:
23                        visited.add(neighbor)
24                        queue.append(neighbor)
25        return height
26
27    min_height = float('inf')
28    result = []
29    for node in range(n):
30        h = bfs_height(node)
31        if h < min_height:
32            min_height = h
33            result = [node]
34        elif h == min_height:
35            result.append(node)
36
37    return result

Time: O(n²) — each of the n BFS passes visits every node and edge.
Space: O(n) — adjacency list and the visited set used per BFS call.

Approach 2 — Leaf Trimming

Iteratively strip all current leaf nodes (degree 1) in rounds until at most 2 nodes remain; those survivors are the MHT roots.

Build an adjacency list and a degree array; guard the n=1 case up front.
Collect the initial leaves: all nodes with degree 1.
While more than 2 nodes remain, subtract the current leaf count from remaining.
For each leaf's neighbor, decrement its degree; if it drops to exactly 1, it becomes the next round's leaf.
Replace leaves with the new leaf list and repeat.
Return the final leaf list — these are the 1 or 2 center nodes.

1from typing import List
2
3def findMinHeightTrees(n: int, edges: List[List[int]]) -> List[int]:
4    if n == 1:
5        return [0]
6
7    degree = [0] * n
8    adj = [[] for _ in range(n)]
9    for u, v in edges:
10        adj[u].append(v)
11        adj[v].append(u)
12        degree[u] += 1
13        degree[v] += 1
14
15    leaves = [node for node in range(n) if degree[node] == 1]
16    remaining = n
17
18    while remaining > 2:
19        remaining -= len(leaves)
20        next_leaves = []
21        for leaf in leaves:
22            for neighbor in adj[leaf]:
23                degree[neighbor] -= 1
24                if degree[neighbor] == 1:  # neighbor is now exposed as a leaf
25                    next_leaves.append(neighbor)
26        leaves = next_leaves
27
28    return leaves

Time: O(n) — each node and edge is touched at most twice across all trimming rounds.
Space: O(n) — adjacency list and degree array.

Complexity Summary

Approach	Time	Space	When to use
Brute Force BFS	O(n²)	O(n)	Only for tiny inputs (n < 200) where code simplicity matters more than speed
Leaf Trimming	O(n)	O(n)	Always — linear time with a clean, direct implementation

Common Mistakes

Forgetting the n=1 edge case — a single isolated node has degree 0, so the initial leaves list is empty and the while loop returns nothing; guard this at the top.
Using remaining >= 2 instead of remaining > 2 — this exits the loop one round too early, stripping the actual center nodes and returning an empty list.
Checking degree[neighbor] <= 1 or == 0 instead of == 1 — if two leaves both connect to the same internal node in the same round, its degree goes 2 → 1 → 0; checking == 1 adds it exactly once (correctly), while <= 1 would add it twice.
Forgetting that edges are undirected — building only adj[u].append(v) without the reverse adj[v].append(u) leaves half the edges missing and produces wrong degree counts.
Assuming there can be more than 2 MHT roots — a tree's center is always 1 or 2 nodes, so remaining > 2 as the loop condition is always sufficient to converge on the correct answer.

Minimum Height Trees — Solution