LeetCode 310 Minimum Height Trees - Implementation

This works like BFS, but you start from the outside and move in.

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

    degree = array of size n, all 0
    adj = array of n empty lists
    q = empty queue

    for (a, b) in edges:
        adj[a].add(b)
        adj[b].add(a)
        degree[a] = degree[a] + 1
        degree[b] = degree[b] + 1

    for i from 0 to n - 1:
        if degree[i] == 1:
            q.push(i)

    remainingNodes = n
    while remainingNodes > 2:
        sz = q.size()
        remainingNodes = remainingNodes - sz
        for each of sz times:
            u = q.pop()
            for v in adj[u]:
                degree[v] = degree[v] - 1
                if degree[v] == 1:
                    q.push(v)

    return q as list

This runs in $O(n)$ time and uses $O(n)$ space.