A tree is an undirected graph in which any two vertices are connected by&nbsp;exactly&nbsp;one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of n nodes&nbsp;labelled from 0 to n - 1, and an array of&nbsp;n - 1&nbsp;edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes&nbsp;ai and&nbsp;bi in the tree,&nbsp;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))&nbsp; are called minimum height trees (MHTs).

Return a list of all MHTs' root labels.&nbsp;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.

&nbsp;
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]


&nbsp;
Constraints:


	1 &lt;= n &lt;= 2 * 104
	edges.length == n - 1
	0 &lt;= ai, bi &lt; 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.


class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n==0:
            return []
        if n==1:return [0]
        adj=[[] for i in range (n)]
        degree=[0]*n
        for i in edges:
            adj[i[0]].append(i[1])
            adj[i[1]].append(i[0])
            degree[i[0]]+=1
            degree[i[1]]+=1
            
        print(adj)
        q=[]
        for i in range(n):
            if degree[i]==1:
                q.append(i)
                
        while n>2:
            size=len(q)
            n-=size
            while size>0:
                v=q.pop(0)
                for i in adj[v]:
                    degree[i]-=1
                    if degree[i]==1:
                        q.append(i)
                size-=1
        return q
                
            
        
class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if(edges.length == 0) {
            List<Integer> al = new ArrayList<>();
            al.add(0);
            return al;
        }
        HashMap<Integer, Set<Integer>> map = new HashMap<>(); // map == graph
        int [] degree = new int[n];
        for(int [] edge : edges){
            int src = edge[0];
            int dest = edge[1];
            map.putIfAbsent(src, new HashSet<>());
            map.get(src).add(dest);
            map.putIfAbsent(dest, new HashSet<>());
            map.get(dest).add(src);
            degree[src]++;
            degree[dest]++;
        }
        Queue<Integer> q = new ArrayDeque<>();
        for(int i = 0; i < degree.length; i++){
            if(degree[i] == 1){
                q.offer(i);
            }
        }
        int count = n;
        while(count > 2){
            int size = q.size();
            count -= size;
            while(size-- > 0){
                Integer src = q.poll();

                for(Integer connection : map.get(src)){
                    degree[connection]--;
                    if(degree[connection] == 1){
                        q.offer(connection);
                    }
                }
            }
        }
        return new ArrayList<>(q);
    }
}
class Solution {
public:
    int getheight(vector<int> a[],int sv,int n)
    {
        int lvl = 0;
        vector<int> vis(n,0);
        queue<int> q;
        q.push(sv);
        vis[sv] = 0;
        while(q.size())
        {
            int sz = q.size();
            lvl++;
            while(sz--)
            {
                int curr = q.front();
                q.pop();
                vis[curr] = 1;
                
                for(auto it:a[curr])
                {
                    if(vis[it]==0)
                    {
                        q.push(it);
                    }
                }
            }
        }
        return lvl;
    }
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<int> a[n];
        vector<int> indegree(n,0);
        for(auto it:edges)
        {
            a[it[0]].push_back(it[1]);
            a[it[1]].push_back(it[0]);
            indegree[it[0]]++;
            indegree[it[1]]++;
        }
        
        //cutting leafs whose indegree is 1
        queue<int> q;
        vector<int> ans;
        for(int i = 0;i<n;i++)
        {
            if(indegree[i]==1)
            {
                q.push(i);
                indegree[i]--;
            }
        }
        
        while(q.size())
        {
            int sz=q.size();
            ans.clear();
            while(sz--)
            {
                int curr = q.front();
                q.pop();
                ans.push_back(curr);
                for(auto it:a[curr])
                {
                    indegree[it]--;
                    if(indegree[it]==1)
                        q.push(it);
                }
            }
        }
        
        if(n==1)return {0};
        
        return ans;
        
        
        //brute force gives tle
//         int mn = INT_MAX;
//         unordered_map<int,vector<int>> mp;
//         for(int i = 0;i<n;i++)
//         {
//             int x = getheight(a,i,n);
//             mp[x].push_back(i);
            
//             // cout<<i<<" "<<x<<endl;
            
//             mn = min(mn,x);
//         }
        
//         return mp[mn];
        
    }
};
var findMinHeightTrees = function(n, edges) {
  
    //edge case
    if(n <=0) return [];
    if(n === 1) return [0]
  
  
    let graph ={}
    let indegree  = Array(n).fill(0)
    let leaves = []
    // build graph
    
    for(let [v,e] of edges){
      //as this is undirected graph we will build indegree for both e and v
      if(!(v in graph)) graph[v] = [];
      if(!(e in graph)) graph[e] = [];
      graph[v].push(e)
      graph[e].push(v)
      indegree[v]++
      indegree[e]++
    }
  
  
  // get all nodes with indegree 1
    for(let i =0; i<indegree.length; i++){
      if(indegree[i] === 1) leaves.push(i)
    }
  
  
    let total  = n;
  
    while(total > 2){
      let size = leaves.length
      // as we are removing nodes from our  total
      total -= size;
      
      for(let i =0 ; i<size; i++){
        let vertex = leaves.shift()
        for(let edge of  graph[vertex] ){
          indegree[edge]--
          if(indegree[edge] === 1) leaves.push(edge)
        }
      }
    }
  
  return leaves;
    
};
Minimum Height Trees