Minimum Height Trees - leaves pruning

min_height.cpp

vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        map<int,unordered_set<int>> mp;
        for(int i=0;i<edges.size();i++){
            
                mp[edges[i][0]].insert(edges[i][1]);
                mp[edges[i][1]].insert(edges[i][0]);
            
        }
        vector<int> curr;
        if(n==1){
            curr.push_back(0);
            return curr;
        }
        for(int i=0;i<n;i++){
            if(mp[i].size()==1){
                curr.push_back(i);
            }
        }
        while(true){
        vector<int> temp;
        for(int i=0;i<curr.size();i++){
            for(auto j=mp[curr[i]].begin();j!=mp[curr[i]].end();j++){
                mp[*j].erase(curr[i]);
                if(mp[*j].size()==1)
                    temp.push_back(*j);
            }
        }
        if(temp.size()==0){
            return curr;
        }
        curr = temp;
        }
    }

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. 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).

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

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

Output: [3, 4]

Idea is to find those nodes in the graph that have only one edge. These will be leaves. We remove these leaves and at the same time keep track of new leaves forming up. We remove leaves layer by layer and when the tree becomes empty, the last layer of the leaves represents those nodes for which the tree will have a minimum height.

Implementation starts with converting the input edges into the adjacency list. Then we take the first layer of leaves and store in a vector 'curr'. For these leaves, erase the edges from the adjacency list. After removing the edges check if new leaves are formed if they are, then add it into a temp vector. If no new nodes are added into temp, this means that graph is now empty. Then the content of the curr vector stores the answer. If it is not empty then temp contains new leaves which now becomes curr.