Centroid Finding - Code

Here's the centroid-finding algorithm:

function findCentroid(root, treeSize, removed)
    computeSubtreeSizes(root, -1, removed)

    current := root
    parent := -1
    while true
        heavyChild := -1
        for each child u of current (not removed, u ≠ parent)
            if subtreeSize[u] > treeSize / 2 then
                heavyChild := u
                break
        if heavyChild = -1 then
            return current
        parent := current
        current := heavyChild

The $removed$ array marks nodes already processed in previous decomposition levels.