LeetCode 1483 - Kth Ancestor of a Tree Node

LeetCode Problem 1483

Difficulty: 🔴 Hard
Topics: Binary Search, Dynamic Programming, Bit Manipulation, Tree, Depth-First Search, Breadth-First Search, Design

Solution

Problem Understanding

The problem gives us a rooted tree with n nodes labeled from 0 to n - 1. Instead of providing the tree as adjacency lists or edges, the input is represented using a parent array. For every node i, parent[i] tells us which node is its direct parent. The root node is 0, and since the root has no parent, parent[0] = -1.

We need to design a data structure that can efficiently answer queries of the form:

What is the kth ancestor of node node?

An ancestor is a node encountered while moving upward toward the root. The first ancestor is the parent, the second ancestor is the grandparent, and so on.

For example, if the path upward from a node is:

7 -> 5 -> 2 -> 0

then:

• 1st ancestor is 5
• 2nd ancestor is 2
• 3rd ancestor is 0
• 4th ancestor does not exist, so the answer is -1

The constraints are extremely important:

• n can be as large as 5 * 10^4
• There can also be up to 5 * 10^4 queries

A naive approach that walks upward one step at a time for every query could become too slow in the worst case. Imagine a chain-like tree where every node has exactly one child. A single query might require traversing tens of thousands of nodes.

The problem guarantees that the input always forms a valid tree rooted at node 0. This means:

• Every node except the root has exactly one parent
• There are no cycles
• Every node is reachable from the root

Important edge cases include:

• Querying an ancestor higher than the root, which should return -1
• Querying the root node itself, where every positive k returns -1
• Deep chain-shaped trees, which are worst-case inputs for naive traversal
• Very large values of k
• Repeated queries, which strongly suggests preprocessing is worthwhile

Approaches

Brute Force Approach

The most straightforward solution is to answer each query by repeatedly moving upward through the parent array.

For a query (node, k):

1. Move from node to parent[node]
2. Decrease k
3. Continue until either:

• k == 0, meaning we found the ancestor
• the node becomes -1, meaning no such ancestor exists

This works because every upward step directly follows the definition of an ancestor.

However, this approach is inefficient for large inputs. In the worst case, the tree may look like a linked list of length n. A single query could then require O(n) time. Since there may be 5 * 10^4 queries, the total runtime could become O(n * q), which is too slow.

Optimal Approach, Binary Lifting

The key observation is that repeatedly moving upward one node at a time is wasteful.

Instead of storing only the immediate parent of each node, we can preprocess larger jumps:

• 1-step ancestor
• 2-step ancestor
• 4-step ancestor
• 8-step ancestor
• and so on

This technique is called Binary Lifting.

The idea comes from binary representation of numbers. Any integer k can be written as a sum of powers of two.

For example:

13 = 8 + 4 + 1

So instead of moving upward 13 times individually, we can:

• jump 8 ancestors
• then jump 4 ancestors
• then jump 1 ancestor

This reduces query time dramatically.

We preprocess a table:

up[node][j]

where:

up[node][j] = 2^j-th ancestor of node

Using dynamic programming:

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

This means:

• the 4th ancestor is the 2nd ancestor of the 2nd ancestor
• the 8th ancestor is the 4th ancestor of the 4th ancestor

Since powers of two grow exponentially, each query only needs O(log n) jumps.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k) per query	O(1)	Walk upward one parent at a time
Optimal	O(log n) per query	O(n log n)	Uses binary lifting preprocessing

Algorithm Walkthrough

Binary Lifting Preprocessing

We construct a table where each entry stores ancestors at powers of two distances.

Suppose:

up[node][j]

means the 2^j-th ancestor of node.

Steps

1. Compute the maximum number of levels needed.

Since n <= 5 * 10^4, the maximum height relevant to queries is less than 2^16.

We therefore need approximately:

$\log_2(5 \times 10^4) \approx 16$

levels in the binary lifting table. 2. Initialize the first column of the table.

The immediate parent is the 2^0 = 1 ancestor.

So:

up[node][0] = parent[node]

3. Fill the rest of the table using dynamic programming.

If we already know the 2^(j-1) ancestor, then the 2^j ancestor can be found by jumping twice.

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

This works because:

2^j = 2^(j-1) + 2^(j-1)

4. Process queries using binary decomposition of k.

For every bit in k:

• if the bit is set, jump upward by the corresponding power of two
• continue until all bits are processed

5. Stop early if the node becomes -1.

This means we moved above the root and no ancestor exists.

Why it works

The algorithm works because every integer can be uniquely represented in binary form.

If:

k = b0 * 2^0 + b1 * 2^1 + b2 * 2^2 + ...

then the kth ancestor can be found by combining jumps of sizes corresponding to the set bits in k.

The preprocessing table guarantees that every 2^j ancestor lookup is correct. Since larger jumps are built from smaller verified jumps, the dynamic programming relation maintains correctness for the entire table.

Python Solution

from typing import List

class TreeAncestor:

    def __init__(self, n: int, parent: List[int]):
        self.max_power = n.bit_length()

        # up[node][j] = 2^j-th ancestor of node
        self.up = [[-1] * self.max_power for _ in range(n)]

        # First ancestor (2^0 = 1 step)
        for node in range(n):
            self.up[node][0] = parent[node]

        # Build binary lifting table
        for j in range(1, self.max_power):
            for node in range(n):
                prev_ancestor = self.up[node][j - 1]

                if prev_ancestor != -1:
                    self.up[node][j] = self.up[prev_ancestor][j - 1]

    def getKthAncestor(self, node: int, k: int) -> int:

        bit_index = 0

        while k > 0 and node != -1:

            # If current bit is set, jump upward
            if k & 1:
                node = self.up[node][bit_index]

            k >>= 1
            bit_index += 1

        return node

# Your TreeAncestor object will be instantiated and called as such:
# obj = TreeAncestor(n, parent)
# param_1 = obj.getKthAncestor(node,k)

The implementation begins by computing the number of binary lifting levels needed. Python's bit_length() gives the number of bits necessary to represent n, which corresponds to the maximum useful power of two.

The up table is then initialized with -1 values. Each row corresponds to a node, and each column corresponds to a jump size.

The first column stores direct parents. After that, the dynamic programming transition builds larger jumps from smaller ones.

The query function processes the binary representation of k. Every set bit means we should jump upward by the corresponding power of two. Since each jump halves the remaining search space, the operation is logarithmic.

The early termination condition node != -1 prevents invalid table lookups once we move above the root.

Go Solution

package main

type TreeAncestor struct {
	up       [][]int
	maxPower int
}

func Constructor(n int, parent []int) TreeAncestor {

	maxPower := 0
	temp := n

	for temp > 0 {
		maxPower++
		temp >>= 1
	}

	up := make([][]int, n)

	for i := 0; i < n; i++ {
		up[i] = make([]int, maxPower)

		for j := 0; j < maxPower; j++ {
			up[i][j] = -1
		}
	}

	// First ancestor
	for node := 0; node < n; node++ {
		up[node][0] = parent[node]
	}

	// Build binary lifting table
	for j := 1; j < maxPower; j++ {
		for node := 0; node < n; node++ {

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

			if prevAncestor != -1 {
				up[node][j] = up[prevAncestor][j-1]
			}
		}
	}

	return TreeAncestor{
		up:       up,
		maxPower: maxPower,
	}
}

func (this *TreeAncestor) GetKthAncestor(node int, k int) int {

	bitIndex := 0

	for k > 0 && node != -1 {

		if (k & 1) == 1 {
			node = this.up[node][bitIndex]
		}

		k >>= 1
		bitIndex++
	}

	return node
}

/**
 * Your TreeAncestor object will be instantiated and called as such:
 * obj := Constructor(n, parent);
 * param_1 := obj.GetKthAncestor(node,k);
 */

The Go implementation follows the same logic as the Python version. Since Go does not provide a direct equivalent of Python's bit_length(), the number of levels is computed manually using repeated right shifts.

The up table is represented using a two-dimensional slice. All entries are initialized to -1 because Go slices default to 0, which would incorrectly imply node 0 is an ancestor.

The query logic uses bitwise operations exactly as in Python.

Worked Examples

Example 1

Input:

n = 7
parent = [-1,0,0,1,1,2,2]

Tree:

        0
      /   \
     1     2
    / \   / \
   3  4  5  6

Binary Lifting Table

Node	2^0 Ancestor	2^1 Ancestor	2^2 Ancestor
0	-1	-1	-1
1	0	-1	-1
2	0	-1	-1
3	1	0	-1
4	1	0	-1
5	2	0	-1
6	2	0	-1

Query: getKthAncestor(3, 1)

Binary representation:

1 = 001

We use the 2^0 jump.

Step	Current Node	Action
Start	3	Initial node
Jump 1	1	Move to parent

Answer:

1

Query: getKthAncestor(5, 2)

Binary representation:

2 = 010

We use the 2^1 jump.

Step	Current Node	Action
Start	5	Initial node
Jump 2	0	Move to 2nd ancestor

Answer:

0

Query: getKthAncestor(6, 3)

Binary representation:

3 = 011

This means:

3 = 2 + 1

Step	Current Node	Action
Start	6	Initial node
Jump 1	2	Use 2^0 jump
Jump 2	-1	Use 2^1 jump

Answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n) preprocessing, O(log n) per query	Build binary lifting table once, answer queries using binary jumps
Space	O(n log n)	Store ancestors for every node at every power of two

The preprocessing step fills a table of size:

$n \times \log n$

Each query processes the binary representation of k, which contains at most log n bits. This gives logarithmic query complexity.

The tradeoff is increased memory usage in exchange for dramatically faster queries.

Test Cases

from typing import List

class TreeAncestor:

    def __init__(self, n: int, parent: List[int]):
        self.max_power = n.bit_length()
        self.up = [[-1] * self.max_power for _ in range(n)]

        for node in range(n):
            self.up[node][0] = parent[node]

        for j in range(1, self.max_power):
            for node in range(n):
                prev = self.up[node][j - 1]

                if prev != -1:
                    self.up[node][j] = self.up[prev][j - 1]

    def getKthAncestor(self, node: int, k: int) -> int:

        bit = 0

        while k > 0 and node != -1:

            if k & 1:
                node = self.up[node][bit]

            k >>= 1
            bit += 1

        return node

# Example test case
obj = TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2])

assert obj.getKthAncestor(3, 1) == 1  # direct parent
assert obj.getKthAncestor(5, 2) == 0  # grandparent
assert obj.getKthAncestor(6, 3) == -1  # ancestor beyond root

# Single node tree
obj = TreeAncestor(1, [-1])

assert obj.getKthAncestor(0, 1) == -1  # root has no ancestor

# Chain tree
obj = TreeAncestor(5, [-1, 0, 1, 2, 3])

assert obj.getKthAncestor(4, 1) == 3  # immediate parent
assert obj.getKthAncestor(4, 2) == 2  # two levels up
assert obj.getKthAncestor(4, 4) == 0  # root ancestor
assert obj.getKthAncestor(4, 5) == -1  # beyond root

# Star-shaped tree
obj = TreeAncestor(6, [-1, 0, 0, 0, 0, 0])

assert obj.getKthAncestor(5, 1) == 0  # parent is root
assert obj.getKthAncestor(5, 2) == -1  # no grandparent

# Large k value
obj = TreeAncestor(3, [-1, 0, 1])

assert obj.getKthAncestor(2, 100) == -1  # huge k

# Repeated queries
obj = TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2])

assert obj.getKthAncestor(4, 1) == 1  # repeated lookup
assert obj.getKthAncestor(4, 2) == 0  # repeated lookup
assert obj.getKthAncestor(4, 3) == -1  # repeated lookup

Test Summary

Test	Why
Example from statement	Verifies correctness against official examples
Single node tree	Tests minimal input size
Chain-shaped tree	Tests worst-case depth
Star-shaped tree	Tests shallow hierarchy
Large k value	Ensures algorithm handles oversized jumps correctly
Repeated queries	Confirms preprocessing supports efficient reuse

Edge Cases

One important edge case is querying ancestors above the root. For example, in a chain of length 3, asking for the 10th ancestor should return -1. This can easily cause invalid indexing bugs if the implementation keeps jumping after reaching the root. The solution handles this safely by stopping once the current node becomes -1.

Another critical case is a tree containing only the root node. Since the root has no parent, every ancestor query must return -1. Some implementations incorrectly assume at least one valid ancestor exists. Here, the binary lifting table correctly initializes the root's ancestors as -1, so all queries behave properly.

A deep chain-shaped tree is also significant because it exposes the weakness of naive traversal. In such a tree, each query could require traversing tens of thousands of nodes. Binary lifting avoids this entirely by decomposing jumps into powers of two, guaranteeing logarithmic query time even in the worst possible tree structure.

A final subtle edge case involves very large values of k. Even if k greatly exceeds the tree height, the algorithm remains efficient because it only processes the binary bits of k. Once the traversal moves above the root, the node becomes -1 and further processing stops safely.