# [leetcode] 310. Minimum Height Trees

## Minimum Height Trees

For a 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:

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

```        0
|
1
/ \
2   3
```

return ``

Example 2:

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

```     0  1  2
\ | /
3
|
4
|
5
```

return `[3, 4]`

Hint:

1. How many MHTs can a graph have at most?

Note:

(1) According to the definition of tree on Wikipedia: “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.”

(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

DP + DFS
Algorithm is as follows, but it is too slow. It costs about 1600ms to execute. ```class Solution {
public:
int MAX_INT = 0x7fffffff;
unordered_map<int, unordered_map<int, int>> heights;// store heights given vertex and edge
unordered_map<int, vector<int> >graph;
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
int height = MAX_INT;
vector<int> res;
// build graph
graph.clear();
heights.clear();
for(auto it = edges.begin(); it != edges.end(); it++){
if(graph.find(it->first) == graph.end()){
graph[it->first] = vector<int>();
}
if(graph.find(it->second) == graph.end()){
graph[it->second] = vector<int>();
}
graph[it->first].push_back(it->second);
graph[it->second].push_back(it->first);
}

// for each vertex in graph
for(int i = 0; i < n; i++){
int localHeight = 0;
for(auto it = graph[i].begin(); it != graph[i].end(); it++){
localHeight = max(localHeight, _MHT(i, *it));
}
if(height == localHeight){
res.push_back(i);
}else if(localHeight < height){
res.clear();
res.push_back(i);
}
height = min(localHeight, height);
}
return res;
}
//pv : previous vertex, v: current vertex
int _MHT(int pv, int v){
int h = getHeight(pv, v);
if(h >= 0){
return h;
}
else{
h = 0;
for(auto it = graph[v].begin(); it != graph[v].end(); it++){
if(*it != pv){
h = max(_MHT(v, *it) + 1, h);
}
}
setHeight(pv, v, h);
return h;
}
}

int getHeight(int pv, int v){
if(heights.find(pv) == heights.end() || heights[pv].find(v) == heights[pv].end()){
return -1;
}else{
return heights[pv][v];
}
}
void setHeight(int pv, int v, int h){
if(heights.find(pv) == heights.end()){
heights[pv] = unordered_map<int, int>();
}
heights[pv][v] = h;
}
};``` ### Topological sort like algorithm. O(V+E)

A better, easier to understand solution
We perform topological sort to the given graph. The rest elements in the last iteration are what we want. We can even find them without calculate their minimum height!
In this question, the given tree-like graph is an undirected graph, but topological sort is applicable only to directed graph. We have to modify the original topological sort algorithm. Different from a typical topological sort algorithm which is described in wikipedia https://en.wikipedia.org/wiki/Topological_sorting . We maintain two queues – readyQ and runningQ – in the algorithm. This idea is inspired by the process states (ready, running, block, zombie) in operating systems. Each time when runningQ is empty, we check whether we have ever pushed all vertices in either queue, which is indicated by restN == 0. If restN == 0, elements in readyQ is what we want. Otherwise, we swap readyQ and runningQ and enter the next iteration.
```// Topological sort
// O(V+E)
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
unordered_map<int, unordered_set<int>> graph;
vector<int> inDegree = vector<int>(n, 0);
vector<int> res;
// extreme case
if(n == 1){
res.push_back(0);
return res;
}
// build indegree vector
for(auto it = edges.begin(); it != edges.end(); it++){
inDegree[it->first]++;
inDegree[it->second]++;
if(graph.find(it->first) == graph.end()){
graph[it->first] = unordered_set<int>();
}
if(graph.find(it->second) == graph.end()){
graph[it->second] = unordered_set<int>();
}
graph[it->first].insert(it->second);
graph[it->second].insert(it->first);
}
// find all vetices with indegree 1
int restN = n;
for(int i = 0; i < n; i++){
if(inDegree[i] == 1){
restN--;
}
}
while(restN > 0){
while(!runningQ.empty()){
int v = runningQ.front();
runningQ.pop();
for(auto it = graph[v].begin(); it != graph[v].end(); it++){
if(--inDegree[*it] == 1){
restN--;
}
// remove edge
graph[*it].erase(v);
}
}
} 