> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Minimum Height Trees Python Solution

> Tested Python solution for LeetCode 310 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 310, Medium. Topics: Depth-First Search, Breadth-First Search, Graph, Topological Sort. [View on LeetCode](https://leetcode.com/problems/minimum-height-trees/description/).

Generate this problem as a practice environment: tested reference solution, 12 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 310   # by problem number
lcpy gen -s minimum_height_trees   # by problem name
```

## 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 (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 **height** of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

### Examples

\<img alt="" src="[https://assets.leetcode.com/uploads/2020/09/01/e1.jpg](https://assets.leetcode.com/uploads/2020/09/01/e1.jpg)" style="width: 800px; height: 213px;" />

```
Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.
```

\<img alt="" src="[https://assets.leetcode.com/uploads/2020/09/01/e2.jpg](https://assets.leetcode.com/uploads/2020/09/01/e2.jpg)" style="width: 800px; height: 321px;" />

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

### 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.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_height_trees/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_height_trees/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import defaultdict, deque


class Solution:
    # Time: O(V)
    # Space: O(V)
    def find_min_height_trees(self, n: int, edges: list[list[int]]) -> list[int]:
        if n == 1:
            return [0]

        graph = defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)

        leaves = deque([i for i in range(n) if len(graph[i]) == 1])

        remaining = n
        while remaining > 2:
            size = len(leaves)
            remaining -= size
            for _ in range(size):
                leaf = leaves.popleft()
                neighbor = graph[leaf].pop()
                graph[neighbor].remove(leaf)
                if len(graph[neighbor]) == 1:
                    leaves.append(neighbor)

        return list(leaves)
```

## Complexity

| Time | Space |
| ---- | ----- |
| O(V) | O(V)  |

## Tags

[Grind 75](/catalog/grind-75), [Grind](/catalog/grind), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).