Untitled

/* a clever implementation of the breadth-first search (BFS) algorithm, where instead of starting from one node, we start from the outermost nodes (leaves) and move towards the center. This approach ensures that the last nodes remaining will be the ones that give us the MHTs.
 */

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<int> res;
        if(n==1) {
            res.push_back(0);
            return res;
        }
        vector<vector<int>> adj(n);
        vector<int> deg(n,0);
        for(int i=0;i<edges.size();i++){
            int x=edges[i][0] ,y =edges[i][1];
            adj[x].push_back(y);
            adj[y].push_back(x);
            deg[x]++;
            deg[y]++;
        }
        queue<int> q;
        for(int i=0;i<n;i++) {
            if(deg[i]==1) q.push(i); //put all 1 degree nbrs(edges) into the queue
        }

         while(n>2){ // there can be max 2 nodes that give max height .. so only 2 max MHTs
            int s=q.size();
            n-=s; // n-s possible nodes left after discarding  s nodes */
            while(s>0){ //it needs to be s not q.size() , 
                int f=q.front();
                q.pop();
                for(auto nbr:adj[f]){
                    deg[nbr]--;
                    if(deg[nbr]==1) q.push(nbr);// push all new edge nodes with deg 1 into the queue, all nodes will be pushed is guarranted by proof
                }
                s--;
            }
        }// outer while loop needed for s

        
        while(!q.empty()){
            int f=q.front();
            res.push_back(f);
            q.pop();
        }
        return res;        
    }
};