# Minimum Height Trees

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.

Example 1:

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

Example 2:

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

Constraints:

• `1 <= n <= 2 * 104`
• `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:

```class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if n <= 2:
return [x for x in range(n)]

neighbours = {i: [] for i in range(n)}

for e1, e2 in edges:
neighbours[e1].append(e2)
neighbours[e2].append(e1)

leaves = []

for neighbour in neighbours:
if len(neighbours[neighbour]) == 1:
leaves.append(neighbour)

min_height = n

while min_height > 2:
min_height -= len(leaves)

tmp = []
for leaf in leaves:
for neighbour in neighbours[leaf]:
neighbours[neighbour].remove(leaf)
if len(neighbours[neighbour]) == 1:
tmp.append(neighbour)
leaves = tmp
return leaves
```

Uk01 on Feb 07, 2022 at 08:02 am

If you like dEexams.com and would like to contribute, you can write your article here or mail your article to admin@deexams.com . See your article appearing on the dEexams.com main page and help others to learn.

×