 # Minimum Height Trees

## Problem Statement

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.

## Sample Test Cases

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

0
|
1
/ \
2   3

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

0  1  2
\ | /
3
|
4
|
5

Output: [3, 4]```

## Problem Solution

Gather all leaves in a queue first. At each iteration, destroy all leaves, destroy the edges that they form in the graph, then add their neighbors to the queue, iff the neighbor is a leaf.

1. We initialize a queue of leaf nodes after creating the graph.
2. How do we know which are leaf nodes? Keep track of in-degree using an array.
3. Now, for the current queue of leaf nodes, we shall remove them from graph, then remove the edges they’re connected to, then update the in-degree of their neighbors.
4. After updating the neighbor’s in-degree, see if we can add it into the queue of leaf nodes
5. Repeat till we’ve 1 or 2 leaf nodes

## Complexity Analysis

Time Complexity: O(n) Because each node will be processed exactly once. They go into the queue of leaves once, and they exit (at most) once.

Space Complexity: Graph creation takes O(E) space ie no of edges to be included.

## Code Implementation

```#include <bits/stdc++.h>
using namespace std;

// This class represents a undirected graph using adjacency list

class Graph
{
public:
int V; // No. of vertices

vector<int> degree;

Graph(int V);
// function to get roots which give minimum height
vector<int> rootForMinimumHeight();
};

Graph::Graph(int V)
{
this->V = V;
for (int i = 0; i < V; i++)
degree.push_back(0);
}

// degree by 1
{
degree[v]++;
degree[w]++;
}

// Method to return roots which gives minimum height to tree
vector<int> Graph::rootForMinimumHeight()
{
queue<int> q;

// first enqueue all leaf nodes in queue
for (int i = 0; i < V; i++)
if (degree[i] == 1)
q.push(i);

// loop untill total vertex remains less than 2
while (V > 2)
{
for (int i = 0; i < q.size(); i++)
{
int t = q.front();
q.pop();
V--;

// for each neighbour, decrease its degree and
// if it become leaf, insert into queue
list<int>::iterator j;
{
degree[*j]--;
if (degree[*j] == 1)
q.push(*j);
}
}
}

// copying the result from queue to result vector
vector<int> res;
while (!q.empty())
{
res.push_back(q.front());
q.pop();
}
return res;
}

// Driver code to test above methods
int main()
{
Graph g(6);