Minimum Height Trees

The key idea

The roots of a minimum height tree are the center(s) of the tree, which always sit at the middle of its longest path. Peel away leaves layer by layer from the outside in; the last 1 or 2 nodes left standing are the centroids and the only answers.

Problem

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 (that is, min(h)) are called minimum height trees (MHTs).

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

The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

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.

Examples

Input: n = 4, edges = [[1,0],[1,2],[1,3]] Output: [1]

Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] Output: [3,4]

Input: n = 1, edges = [] Output: [0]

Complexity

Time: O(n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →