Minimum Height Trees solution and explanation

#include <vector>
#include <queue>
using namespace std;

vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
    if (n == 1) return {0};

    vector<int> degree(n, 0);
    vector<vector<int>> adj(n);

    for (const auto& edge : edges) {
        adj[edge[0]].push_back(edge[1]);
        adj[edge[1]].push_back(edge[0]);
        degree[edge[0]]++;
        degree[edge[1]]++;
    }

    queue<int> leaves;
    for (int i = 0; i < n; i++) {
        if (degree[i] == 1) leaves.push(i);
    }

    int count = n;
    while (count > 2) {
        int size = leaves.size();
        count -= size;

        for (int i = 0; i < size; i++) {
            int leaf = leaves.front();
            leaves.pop();
            degree[leaf]--;

            for (int neighbor : adj[leaf]) {
                if (--degree[neighbor] == 1) {
                    leaves.push(neighbor);
                }
            }
        }
    }

    vector<int> result;
    while (!leaves.empty()) {
        result.push_back(leaves.front());
        leaves.pop();
    }

    return result;
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_NODES 20000

int* findMinHeightTrees(int n, int** edges, int edgesSize, int* edgesColSize, int* returnSize){
    if (n == 1) {
        *returnSize = 1;
        int* res = (int*)malloc(sizeof(int));
        res[0] = 0;
        return res;
    }
    
    int* degrees = (int*)calloc(n, sizeof(int));
    int* adj[MAX_NODES];
    for (int i = 0; i < n; ++i) adj[i] = (int*)malloc(sizeof(int) * n);
    int adjLen[MAX_NODES] = {0};

    for (int i = 0; i < edgesSize; ++i) {
        int u = edges[i][0], v = edges[i][1];
        adj[u][adjLen[u]++] = v;
        adj[v][adjLen[v]++] = u;
        degrees[u]++;
        degrees[v]++;
    }
    
    int queue[MAX_NODES];
    int front = 0, rear = 0;
    for (int i = 0; i < n; ++i) {
        if (degrees[i] == 1) {
            queue[rear++] = i;
        }
    }

    int count = n;
    while (count > 2) {
        int size = rear - front;
        count -= size;
        for (int i = 0; i < size; ++i) {
            int leaf = queue[front++];
            degrees[leaf]--;
            for (int j = 0; j < adjLen[leaf]; ++j) {
                int neighbor = adj[leaf][j];
                if (--degrees[neighbor] == 1) {
                    queue[rear++] = neighbor;
                }
            }
        }
    }

    *returnSize = rear - front;
    int* res = (int*)malloc((*returnSize) * sizeof(int));
    for (int i = 0; front < rear; ++front, ++i) {
        res[i] = queue[front];
    }
    
    free(degrees);
    for (int i = 0; i < n; ++i) free(adj[i]);

    return res;
}

from collections import defaultdict, deque

def findMinHeightTrees(n, edges):
    if n == 1:
        return [0]

    adj = defaultdict(set)
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)

    leaves = deque(i for i in range(n) if len(adj[i]) == 1)

    while n > 2:
        n -= len(leaves)
        new_leaves = deque()
        while leaves:
            leaf = leaves.popleft()
            for neighbor in adj[leaf]:
                adj[neighbor].remove(leaf)
                if len(adj[neighbor]) == 1:
                    new_leaves.append(neighbor)
            adj.pop(leaf)
        leaves = new_leaves

    return list(leaves)

import java.util.*;

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Collections.singletonList(0);

        List<Set<Integer>> adj = new ArrayList<>(n);
        for (int i = 0; i < n; i++) adj.add(new HashSet<>());
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        int[] degree = new int[n];
        for (int i = 0; i < n; i++) degree[i] = adj.get(i).size();

        Queue<Integer> leaves = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) leaves.offer(i);
        }

        while (n > 2) {
            int size = leaves.size();
            n -= size;
            for (int i = 0; i < size; i++) {
                int leaf = leaves.poll();
                for (int neighbor : adj.get(leaf)) {
                    adj.get(neighbor).remove(leaf);
                    if (--degree[neighbor] == 1) leaves.offer(neighbor);
                }
            }
        }

        return new ArrayList<>(leaves);
    }
}

function findMinHeightTrees(n: number, edges: number[][]): number[] {
    if (n === 1) {
        return [0];
    }
    const g: number[][] = Array.from({ length: n }, () => []);
    const degree: number[] = Array(n).fill(0);
    for (const [a, b] of edges) {
        g[a].push(b);
        g[b].push(a);
        ++degree[a];
        ++degree[b];
    }
    const q: number[] = [];
    for (let i = 0; i < n; ++i) {
        if (degree[i] === 1) {
            q.push(i);
        }
    }
    const ans: number[] = [];
    while (q.length > 0) {
        ans.length = 0;
        const t: number[] = [];
        for (const a of q) {
            ans.push(a);
            for (const b of g[a]) {
                if (--degree[b] === 1) {
                    t.push(b);
                }
            }
        }
        q.splice(0, q.length, ...t);
    }
    return ans;
}

func findMinHeightTrees(n int, edges [][]int) (ans []int) {
	if n == 1 {
		return []int{0}
	}
	g := make([][]int, n)
	degree := make([]int, n)
	for _, e := range edges {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
		degree[a]++
		degree[b]++
	}
	q := []int{}
	for i, d := range degree {
		if d == 1 {
			q = append(q, i)
		}
	}
	for len(q) > 0 {
		ans = []int{}
		for i := len(q); i > 0; i-- {
			a := q[0]
			q = q[1:]
			ans = append(ans, a)
			for _, b := range g[a] {
				degree[b]--
				if degree[b] == 1 {
					q = append(q, b)
				}
			}
		}
	}
	return
}