Kth Ancestor of a Tree Node — LC 1483 Binary Lifting

Problem Statement#

LeetCode 1483 — Kth Ancestor of a Tree Node | Difficulty: Medium

You are given a tree with n nodes numbered from 0 to n-1 and an array parent where parent[i] is the parent of node i (the root's parent is -1). Implement the class TreeAncestor:

• TreeAncestor(int n, int[] parent) — initializes the object
• getKthAncestor(int node, int k) — returns the k-th ancestor of node, or -1 if no such ancestor

Constraints:

• 1 <= k <= n <= 5 * 10^4
• parent[0] == -1 (root node)
• 0 <= parent[i] < n for all i > 0
• 0 <= node < n
• Up to 5 * 10^4 queries

Input:  n=7, parent=[-1,0,0,1,1,2,2], queries: getKthAncestor(3,1), getKthAncestor(5,2), getKthAncestor(6,3)
Output: 1, 0, -1

Why This Problem Matters#

Kth Ancestor is the gateway problem to binary lifting — a technique that appears in Lowest Common Ancestor (LCA) algorithms, competitive programming, and range query problems. Amazon asks it in system design contexts (hierarchical data traversal) and coding rounds. The naive approach of walking up k steps is O(k) per query, which times out for large k with many queries. Binary lifting reduces this to O(log k) per query.

Binary lifting is the same "doubling trick" used in fast exponentiation (x^n in O(log n)) applied to tree traversal. Learning this pattern unlocks LCA in O(log n), range minimum queries with sparse tables, and Euler tour techniques.

The Core Insight#

Precompute a 2D table: up[node][j] = the 2^j-th ancestor of node.

Base case: up[node][0] = parent[node] (1-step ancestor). Transition: up[node][j] = up[up[node][j-1]][j-1] (2^j ancestor = 2^(j-1) ancestor of 2^(j-1) ancestor).

To find the k-th ancestor, decompose k in binary. If bit j is set in k, jump 2^j steps from the current node:

k = 6 = 110 in binary → jump 2 steps, then jump 4 steps (total 6)

If at any point the current node becomes -1 (no ancestor), return -1.

LOG = 16 covers trees of depth up to 65535, sufficient for n up to 5 * 10^4.

Visual Dry Run#

Tree: parent = [-1, 0, 0, 1, 1, 2, 2]

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

Binary lifting table (up[node][j]):

getKthAncestor(3, 1): k=1=001 binary → jump 1 step → node 1. Answer: 1 getKthAncestor(5, 2): k=2=010 binary → jump 2 steps → node 0. Answer: 0 getKthAncestor(6, 3): k=3=011 binary → jump 1 step → node 2; jump 2 steps → -1. Answer: -1

Solution (Optimal)#

class TreeAncestor:
    def __init__(self, n: int, parent: list):
        LOG = 16  # 2^16 = 65536 > max n = 50000
        self.up = [[-1] * LOG for _ in range(n)]
 
        # Base case: direct parent (2^0 = 1 step)
        for i in range(n):
            self.up[i][0] = parent[i]
 
        # Fill table: 2^j ancestor = 2^(j-1) ancestor of 2^(j-1) ancestor
        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: int, k: int) -> int:
        for j in range(16):
            if (k >> j) & 1:  # if bit j is set in k
                node = self.up[node][j]
                if node == -1:
                    return -1
        return node

class TreeAncestor {
    constructor(n, parent) {
        const LOG = 16;
        this.up = Array.from({length: n}, () => Array(LOG).fill(-1));
 
        for (let i = 0; i < n; i++) this.up[i][0] = parent[i];
 
        for (let j = 1; j < LOG; j++) {
            for (let i = 0; i < n; i++) {
                if (this.up[i][j - 1] !== -1) {
                    this.up[i][j] = this.up[this.up[i][j - 1]][j - 1];
                }
            }
        }
    }
 
    getKthAncestor(node, k) {
        for (let j = 0; j < 16; j++) {
            if ((k >> j) & 1) {
                node = this.up[node][j];
                if (node === -1) return -1;
            }
        }
        return node;
    }
}

Preprocessing: O(n log n) — fill the n x LOG table Query: O(log k) — decompose k in binary and make at most LOG jumps Space: O(n log n) — the 2D table

Common Mistakes#

• Using LOG = 16 but the constraints allow n up to 5*10^4 — LOG=16 is sufficient since 2^16 = 65536 > 50000
• Not checking if up[i][j-1] != -1 before filling up[i][j] — accessing up[-1][j-1] would be an index error
• Iterating j in the wrong order in preprocessing (must go from j=1 upward, not downward)
• Returning node instead of -1 when node becomes -1 mid-traversal in getKthAncestor

Interview Tips#

• Explain binary lifting as "same as fast exponentiation, but applied to tree ancestor jumps"
• Draw the up table for a small example before coding
• State preprocessing complexity (O(n log n)) and query complexity (O(log k)) separately
• Mention that this is the foundation for LCA (Lowest Common Ancestor) algorithms

Follow-up Questions#

• How does binary lifting extend to LCA? Find LCA(u, v) by: (1) bring u and v to the same depth using binary lifting, (2) lift both together until they meet.
• What if the tree changes dynamically (nodes added/removed)? Static binary lifting requires recomputation. Use link-cut trees for dynamic connectivity.
• What is the space-optimal approach if queries are offline? Use DFS + stack-based O(1) space ancestor tracking if queries can be answered during the DFS.
• Can binary lifting work for weighted trees? Yes — store the accumulated weight instead of just the ancestor node in the table.

Key Takeaways#

• Binary lifting precomputes the 2^j-th ancestor for each node in O(n log n)
• The recurrence up[i][j] = up[up[i][j-1]][j-1] doubles the jump distance at each level
• Queries decompose k in binary and jump by powers of 2 — O(log k) per query
• Return -1 immediately if any jump leads to -1 (no ancestor at that level)
• LOG = 16 is sufficient for trees up to 65536 nodes; adjust for larger trees
• This technique is the foundation for O(log n) LCA, range minimum queries, and other doubling algorithms
• The space-time tradeoff: O(n log n) preprocessing enables O(log k) queries instead of O(k)