HLD Construction - Code

Here's the construction:

function buildHLD(root)
    // First DFS: compute subtree sizes
    dfs1(root, -1)

    // Second DFS: assign positions
    currentPos := 0
    dfs2(root, -1, root)

function dfs1(v, parent)
    subtreeSize[v] := 1
    for each child u of v (u ≠ parent)
        dfs1(u, v)
        subtreeSize[v] := subtreeSize[v] + subtreeSize[u]
        if subtreeSize[u] > subtreeSize[heavyChild[v]] then
            heavyChild[v] := u

function dfs2(v, p, head)
    parent[v] := p
    chainHead[v] := head
    pos[v] := currentPos
    currentPos := currentPos + 1

    if heavyChild[v] exists then
        dfs2(heavyChild[v], v, head) // Continue chain

    for each child u of v (u ≠ parent, u ≠ heavyChild[v])
        dfs2(u, v, u) // Start new chain