## # 310. Minimum Height Trees

For an undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

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

0
|
1
/ \
2   3

Output: 
``````

Example 2:

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

0  1  2
\ | /
3
|
4
|
5

Output: [3, 4]
``````

### # Solution

Approach 1: BFS -- in every iteration, remove nodes with degree == 1 until we have 1 or 2 nodes left. Time: O(N).

Approach 2: the result is the midpoint of the longest path in the graph. To find the longest path in the graph, do a dfs from a random node and find the leaf on the otherside across the longest path, and that leaf is one end of the longest path in the graph. Then dfs from that leaf to find the longest path in the graph.

### # Code (Python)

Approach 1:

``````class Solution:
def findMinHeightTrees(self, n, edges):
if n == 1:
return 
adj_list = [set() for _ in range(n)]
for edge in edges:
nodes_left = n
leaves = [i for i in range(n) if len(adj_list[i]) == 1] # first level of BFS
while nodes_left > 2:
nodes_left -= len(leaves)
new_leaves = []
for leave in leaves:
neighbor = adj_list[leave].pop() # set.pop() pops out a random element from the set
if len(adj_list[neighbor]) == 1: # only neighbors' degrees are affected
new_leaves.append(neighbor)
leaves = new_leaves
return leaves
``````

Approach 2:

``````    def findMinHeightTrees(self, n, edges):
if n == 1:
return 
adj_list = [set() for _ in range(n)]
for edge in edges:
if len(global_longest_path) % 2 == 1:
return [global_longest_path[len(global_longest_path)//2]]
else:
return [global_longest_path[len(global_longest_path)//2-1], global_longest_path[len(global_longest_path)//2]]

longest_path = []
return longest_path

if not longest_path or len(longest_path) < len(current_path):
for i in range(len(current_path)):
if i < len(longest_path):
longest_path[i] = current_path[i]
else:
longest_path.append(current_path[i])
return
if node not in current_path:
current_path.append(node)
current_path.pop()
``````

### # Code (C++)

Approach 1:

``````// BFS
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
for (int i = 0; i < edges.size(); ++i)
{
int v1 = edges[i];
int v2 = edges[i];
}
queue<int> q;
for (int v = 0; v < n; ++v)
{
q.push(v);
}
vector<int>res;
int count = 0;
while (!q.empty())
{
if (n - count <= 2) // The result will have at most two nodes.
{
while (!q.empty())
{
res.push_back(q.front());
q.pop();
}
break;
}
int qSize = q.size();
for (int i = 0; i < qSize; ++i)
{
int v1 = q.front();
q.pop();
count++;
q.push(v2);
}
}
return res;
}
};
``````

Approach 2:

``````// DFS - the midpoint of the longest path in the graph.
class Solution {
private:
vector<int> longestPath;
void findLongestPath(vector<int>& path, int start) {
path.push_back(start);
if (link[start].size() == 0 && path.size() > longestPath.size())
longestPath = path;
{
findLongestPath(path, *it);
}
path.pop_back();
}
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
for (int i = 0; i < edges.size(); ++i)
{
int v1 = edges[i];
int v2 = edges[i];