Find all roots of an undirected tree that produce the minimum possible tree height.
Minimum Height Trees
You are given an undirected tree with n nodes labeled 0 to n - 1, and a list of n - 1 edges. Choose any node as the root, and the height of the rooted tree is the number of edges on the longest path from the root to any other node.
Return all node labels that can be chosen as the root so that the tree has the minimum possible height.
If there are multiple valid roots, return all of them in any order.
Goal
Identify the tree's center node(s), which are the root positions that minimize the maximum distance to every other node.
Input Format
n: number of nodes in the treeedges: list of undirected edges, where each edge is[u, v]
The graph is guaranteed to be a tree.
Output Format
- Return a list of node labels that are roots of minimum height trees.
- If multiple answers exist, return all of them in any order.
Constraints
1 <= n <= 2 * $10^{4}$edges.length == n - 10 <= u, v < n- The input graph is connected and acyclic.
Example 1
Input
n = 4 edges = [[1,0],[1,2],[1,3]]
Output
[1]
Explanation
Node 1 is the center of the tree, so rooting at 1 gives the minimum height.
Example 2
Input
n = 6 edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output
[3,4]
Explanation
The tree has two centers, 3 and 4. Either root gives the minimum possible height.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.