Problem Statement
Minimum Height Trees
A tree here means a set of nodes connected by edges with no loops, where you can get from any node to any other node in exactly one way. Picture a connected web of dots and lines with no circles in it. If you pick one node to be the root and hang the whole tree from it, the height is the longest chain of edges from that root down to the farthest node. Different roots give different heights. The question asks: which node or nodes, when used as the root, give the smallest possible height? The answer is the center of the tree, called the centroid. There can be one centroid or two of them, never more. The trick to find the center is to peel off the outer nodes layer by layer, like peeling an onion, until only the middle is left.
Signals to notice
Brute force first
Root the tree at each node, compute height, find minimum. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.
The key insight
Topological peeling: repeatedly remove leaf nodes (degree 1) layer by layer, like peeling an onion. The last 1-2 nodes remaining are the centroids (minimum height tree roots). Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.
Trace it on n=6, edges=[[3,0],[3,1],[3,2],[3,4],[5,4]]
adj: 0:{3} 1:{3} 2:{3} 3:{0,1,2,4} 4:{3,5} 5:{4}
leaves=[0,1,2,5] (degree 1), remaining=6
remaining>2 -> remaining=6-4=2; peel layer
remove 0,1,2 from node 3 -> 3:{4} (deg 1 -> new leaf)
remove 5 from node 4 -> 4:{3} (deg 1 -> new leaf)
leaves=[3,4]; loop check 2>2 is false -> stop
return [3,4]What must stay true
The centroid(s) of a tree are the 1-2 nodes at the very center. Removing leaves brings you closer to the center. The process terminates with 1 or 2 remaining nodes. As long as that statement keeps holding, you can trust the steps built on top of it.
Shape of the loop
build adj sets from edges leaves = all nodes with degree == 1 while remaining > 2: remaining -= len(leaves) for leaf in leaves: drop leaf from each neighbor; if neighbor now degree 1 -> next layer leaves = next layer return leaves
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not handling the case of exactly 2 remaining nodes — a tree can have 1 or 2 centroids. Both are valid answers. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.