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

$ curl repovive.com/roadmaps/graph-theory/binary-lifting/kth-ancestor-implementation

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

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

$ curl repovive.com/roadmaps/graph-theory/binary-lifting/kth-ancestor-implementation

Repovive

Kth Ancestor - Implementation - Binary Lifting | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Kth Ancestor - Implementation

(Pseudocode for class)

Here is the binary lifting implementation:

class TreeAncestor:
    function constructor(n, parent):
        LOG = ceil(log2(n)) + 1
        up = 2D array of size n x LOG, all -1

// Base case: direct parents
        for i from 0 to n - 1:
            up[i][0] = parent[i]

// Fill sparse table
        for j from 1 to LOG - 1:
            for i from 0 to n - 1:
                if up[i][j-1] != -1:
                    up[i][j] = up[up[i][j-1]][j-1]

function getKthAncestor(node, k):
        for j from 0 to LOG - 1:
            if k & (1 << j):
                node = up[node][j]
                if node == -1:
                    return -1
        return node

Time: $O(n \log n)$ preprocessing, $O(\log k)$ per query. Space: $O(n \log n)$ .