#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/tree-fundamentals/peeling-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/tree-fundamentals/peeling-implementation

Repovive

LeetCode 310 Minimum Height Trees - Implementation - Tree Fundamentals | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

LeetCode 310 Minimum Height Trees - Implementation

BFS-like leaf removal

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.