Back to Problems

Minimum Height Trees

Medium
Topological Sort

A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).

Return a list of all MHTs' root labels. You can return the answer in any order.

The insight: The roots of MHTs are the "centroids" of the tree - nodes that are most central. We can find them by repeatedly removing leaf nodes (nodes with degree 1) layer by layer, similar to peeling an onion. The last remaining node(s) are the centroids.

Real-world analogy: Imagine placing a water tower to serve houses in a tree-shaped network. The optimal location minimizes the maximum distance to any house - this is the centroid.

Example 1

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: Node 1 is connected to all other nodes. If we root the tree at node 1, the height is 1 (minimum possible). Any other root gives height 2.

Example 2

Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]
Explanation: Both node 3 and node 4 give minimum height trees with height 2.

Example 3

Input: n = 1, edges = []
Output: [0]
Explanation: Single node tree, the only node is the root.

Constraints

  • •1 <= n <= 2 * 10^4
  • •edges.length == n - 1
  • •0 <= ai, bi < n
  • •ai != bi
  • •All the pairs (ai, bi) are distinct
  • •The given input is guaranteed to be a tree and there will be no repeated edges
Show Hints (6)
Hint 1: What nodes would give the worst (maximum) height? Think about the extremes of the tree.
Hint 2: Leaf nodes (degree 1) are at the periphery. Rooting at a leaf gives maximum height.
Hint 3: What if we remove all leaves? The new leaves are one step closer to the center.
Hint 4: Keep removing leaves layer by layer. What remains?
Hint 5: This is like reverse topological sort - instead of processing in-degree 0, process degree 1.
Hint 6: At most 2 nodes can remain (the centroid(s) of the tree).
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?