Minimum Height Trees

Find all roots that minimize the height of an undirected tree using graph algorithms.

graphs bfs topological tree

Given an integer n (the number of nodes) and an undirected tree with edges as a list of pairs [u, v], return a list of all nodes that, when chosen as the root, yield the minimum possible height for the tree. The height of a rooted tree is the maximum number of edges on a path from the root to any leaf. Nodes are labeled from 0 to n-1. The input is guaranteed to be a valid tree (connected and acyclic). The returned list should be sorted in ascending order. If n == 1, the only node 0 is the answer.

Implement the function `find_min_height_roots(n: int, edges: List[List[int]]) -> List[int]`.

Note: The function signature uses `List` from the `typing` module, but you may also define it without type hints.

Constraints

1 <= n <= 10^4
0 <= edges.length <= n-1
The graph is a valid tree.
The answer list will contain either 1 or 2 nodes.

Example

```python
# Example 1
n = 4
edges = [[1,0],[1,2],[1,3]]
print(find_min_height_roots(n, edges))  # Output: [1]

# Example 2
n = 6
edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
print(find_min_height_roots(n, edges))  # Output: [3,4]

# Example 3
n = 1
edges = []
print(find_min_height_roots(n, edges))  # Output: [0]
```

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Consider what happens when you repeatedly remove leaves (nodes with degree 1) layer by layer.

The middle node(s) of the longest path in the tree become the roots of minimum height trees.

Use BFS-like peeling: initialize a queue with all leaves, remove them while updating degrees, and the last layer will be the answer.

If n is odd, there is exactly one root; if even, there are two adjacent roots.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.