Kth Ancestor - Implementation

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)$.