**Solution**

**Minimum Height Trees** https://leetcode.com/problems/minimum-height-trees/

- The discuss posts are super helpful.
- Brute force would be to try every node and find its height. This is N^2 solution.
- Minimum height tree is rooted at the mid point of the longest path in the tree.
- Here is one insight for this problem: the root of MHT is the middle point of the longest path in the tree; hence there are at most two MHT roots.
- How to find them? We can BFS from the bottom (leaves) to the top until the last level with <=2 nodes. To build the current level from the previous level, we can monitor the degree of each node. If the node has degree of one, it will be added to the current level. Since it only check the edges once, the complexity is O(n).
- Remember a tree has n nodes and n-1 edges.
- https://discuss.leetcode.com/topic/30572/share-some-thoughts

```
class Solution(object):
def findMinHeightTrees(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: List[int]
"""
degree = {k:0 for k in range(n)}
graph = {k:set([]) for k in range(n)}
for edge in edges:
u,v = edge[0], edge[1]
degree[u], degree[v] = degree[u]+1, degree[v]+1
graph[u].add(v)
graph[v].add(u)
leaves = [k for k,v in degree.items() if v == 1]
while leaves and len(graph) > 2:
for leaf in leaves:
v = graph[leaf].pop()
del graph[leaf]
del degree[leaf]
degree[v] -= 1
graph[v].remove(leaf)
leaves = [k for k,v in degree.items() if v == 1]
return list(graph.keys())
```

**How will you find the longest path in a tree?**

- Randomly select any node in the tree and find the longest path from that node. Use DFS to do that. Let the terminal node be x.
- x must be the end-point of the true longest path in the tree.
- Run DFS/BFS from x to find the real longest path in the tree.
- Minimum height tree is rooted at the mid point of this longest path. There can be atmost 2 mid-points or two roots.
- https://www.quora.com/How-does-following-algorithm-for-finding-longest-path-in-tree-work
- https://discuss.leetcode.com/topic/30956/two-o-n-solutions