Kth Ancestor of a Tree Node: Binary Lifting

You are given a tree with n nodes numbered from 0 to n - 1, rooted at node 0. The tree is described by a parent array where parent[i] is the parent of node i (with parent[0] = -1 since the root has no parent). You need to build a TreeAncestor class that supports a single query: given a node and an integer k, return the kth ancestor of that node, or -1 if no such ancestor exists.

This is LeetCode 1483: Kth Ancestor of a Tree Node. A naive approach of climbing one parent at a time takes O(k) per query, which is too slow when k can be up to n = 50,000 and there can be up to 50,000 queries. The solution is binary lifting, a technique that precomputes ancestors at power-of-2 distances so you can answer each query in O(log k) time.

Why this problem matters

Binary lifting is one of the most important techniques in tree algorithms. Beyond this specific problem, it is the foundation for computing Lowest Common Ancestor (LCA) in O(log n) time, which shows up constantly in competitive programming and real-world tree queries. The core idea, precomputing jumps at exponentially increasing distances, is a pattern you will see in many other contexts: sparse tables for range queries, jump pointers in skip lists, and doubling tricks in various DP problems.

If you can implement binary lifting cleanly, you have a building block that unlocks an entire family of efficient tree algorithms.

The key insight

Instead of storing only each node's direct parent, build a 2D table up[node][j] where up[node][j] is the ancestor of node that is exactly 2^j steps above it. The base case is up[node][0] = parent[node]. For larger jumps, use the recurrence:

up[node][j] = up[ up[node][j-1] ][j-1]

This says: to jump 2^j steps, first jump 2^(j-1) steps, then jump 2^(j-1) steps again. Two half-jumps make one full jump.

To answer a query getKthAncestor(node, k), decompose k into its binary representation and make one jump for each set bit. For example, if k = 5 = 101 in binary, you jump 2^0 = 1 step and then 2^2 = 4 steps. At most log(k) jumps are needed.

The solution

class TreeAncestor:
    def __init__(self, n, parent):
        LOG = n.bit_length()
        self.up = [[-1] * LOG for _ in range(n)]
        for i in range(n):
            self.up[i][0] = parent[i]
        for j in range(1, LOG):
            for i in range(n):
                if self.up[i][j - 1] != -1:
                    self.up[i][j] = self.up[self.up[i][j - 1]][j - 1]

    def getKthAncestor(self, node, k):
        j = 0
        while k > 0 and node != -1:
            if k & 1:
                node = self.up[node][j]
            j += 1
            k >>= 1
        return node

Let's walk through each piece:

• LOG = n.bit_length() determines how many columns the table needs. For a tree with n nodes, the maximum depth is n - 1, so we need log2(n) columns. The bit_length() method gives us the number of bits needed to represent n, which is exactly ceil(log2(n)) + 1 for most values.
• self.up = [[-1] * LOG for _ in range(n)] initializes the table with -1, meaning "no ancestor exists at this distance."
• The first loop fills column 0: each node's direct parent.
• The nested loop fills columns 1 through LOG - 1. For each node i and jump power j, if the halfway ancestor exists, look up its ancestor at the same distance. Two half-jumps combine into one full jump.
• In getKthAncestor, we iterate through the bits of k. For each set bit at position j, we jump 2^j steps using the precomputed table. If node ever becomes -1, the ancestor does not exist.

Visual walkthrough

The walkthrough shows two phases. First, the precomputation phase fills the lifting table column by column. Column 0 stores direct parents, column 1 stores grandparents, column 2 stores ancestors at distance 4, and so on. Second, the query phase shows how k is decomposed into powers of 2. For k=3, two jumps (one of size 1 and one of size 2) get us from node 7 to node 0. For k=4 starting at node 5, the single jump of size 4 exceeds the available depth, returning -1.

Complexity analysis

Initialization takes O(n log n). You fill a table with n rows and log n columns. Each cell takes O(1) to compute using the recurrence.

Each query takes O(log k). You iterate through the bits of k, making at most log k jumps. Each jump is an O(1) table lookup.

Space is O(n log n) for the lifting table. Each of the n nodes stores log n ancestors.

The building blocks

1. Power-of-2 ancestor table (binary lifting precomputation)

LOG = n.bit_length()
up = [[-1] * LOG for _ in range(n)]
for i in range(n):
    up[i][0] = parent[i]
for j in range(1, LOG):
    for i in range(n):
        if up[i][j - 1] != -1:
            up[i][j] = up[up[i][j - 1]][j - 1]

The recurrence up[node][j] = up[ up[node][j-1] ][j-1] is the heart of binary lifting. It says: to find the ancestor 2^j steps away, first go 2^(j-1) steps, then go another 2^(j-1) steps from there. This is exactly how exponentiation by squaring works. You double the jump distance with each column, covering exponentially larger distances with just one more column.

2. Binary decomposition for queries

def getKthAncestor(self, node, k):
    j = 0
    while k > 0 and node != -1:
        if k & 1:
            node = self.up[node][j]
        j += 1
        k >>= 1
    return node

Any integer k can be written as a sum of distinct powers of 2. By checking each bit of k and jumping only when the bit is set, you decompose a single large jump into at most log k smaller jumps. This is the same principle behind binary representations in general: any number is uniquely represented by its set bits.

Edge cases

• k = 0: the 0th ancestor of a node is the node itself. The while loop does not execute, so node is returned unchanged.
• k exceeds the depth of the node: the node does not have a kth ancestor. During the jumps, node will become -1, and we return -1.
• Root node queries: getKthAncestor(0, k) for any k > 0 returns -1 since the root has no parent.
• Single node tree: n = 1, parent = [-1]. The only valid query is getKthAncestor(0, 0) = 0. Everything else returns -1.
• Skewed tree (linked list shape): the tree has depth n - 1. The table has log n columns, and queries still run in O(log k) rather than O(k). This is the scenario where binary lifting provides the biggest speedup over naive parent-chasing.

From understanding to recall

You just traced through binary lifting: the doubling recurrence that fills the table and the bit-by-bit decomposition that answers queries. You understand why up[node][j] = up[ up[node][j-1] ][j-1] works and why each query touches at most log k entries.

But when you sit down to code this in an interview, will you remember to initialize the table with -1? Will you remember the loop order (outer loop on j, inner on i) for the precomputation? Will you remember to check node != -1 before making the next jump in the query?

Understanding is not recall. You understood the solution. Recall means you can produce it from scratch under pressure, without mixing up the loop order or forgetting the -1 guard.

Spaced repetition builds recall. You practice typing the solution from memory at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the lifting table and the query function from scratch. After a few repetitions, the pattern is automatic.

Binary lifting is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling it individually is far more effective than grinding random problems and hoping the pattern sticks.

Related posts

• Lowest Common Ancestor - LCA queries benefit from binary lifting
• Binary Tree Maximum Path Sum - Deep tree traversal patterns
• All Nodes Distance K in Binary Tree - Another tree distance/ancestor problem

CodeBricks helps you move from understanding to recall by breaking problems into their core building blocks and drilling them with spaced repetition. Instead of re-solving hundreds of problems, you practice the 60 patterns that cover them all.