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

$ curl repovive.com/roadmaps/data-structures/advanced-trees/centroid-finding-code

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

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

$ curl repovive.com/roadmaps/data-structures/advanced-trees/centroid-finding-code

Repovive

Centroid Finding - Code - Advanced Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Centroid Finding - Code

The implementation

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.