The machine must find all nodes that, when used as the root, produce the tree with the minimum possible height. Any node can be the root, so the brute force of rooting everywhere and measuring each height costs O(n²) — too slow for large n.
The key insight is that the minimum-height roots are exactly the tree's centers. The center is found by peeling: the machine repeatedly removes all current leaves (degree-1 nodes) layer by layer, and when one or two nodes remain, those are the centers. A tree has at most two centers, which is why the answer is always one or two nodes.
The approach has three steps. First, build the adjacency list and handle the special case of a single node. Second, compute degrees, enqueue all leaves, and process layers: remove the leaves, decrement the degrees of their neighbors, and enqueue newly exposed leaves — but only while more than two nodes remain. Third, return the surviving nodes. Each edge is touched at most twice, so time is O(n) and space is O(n).
The trickiest edge case is the two-node tree: both nodes are leaves, and stripping until zero remain would return an empty answer. Stopping at two remaining nodes preserves both centers, and the single-node graph returns [0] before the loop starts.
from collections import deque
def findMinHeightTrees(n, edges):
if n == 1:
return [0]
adj = [[] for _ in range(n)]
degree = [0] * n
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
degree[a] += 1
degree[b] += 1
leaves = deque(i for i in range(n) if degree[i] == 1)
remaining = n
while remaining > 2:
for _ in range(len(leaves)):
leaf = leaves.popleft()
remaining -= 1
for nb in adj[leaf]:
degree[nb] -= 1
if degree[nb] == 1:
leaves.append(nb)
return list(leaves)