#1483

Hard

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Kth Ancestor of a Tree Node

Find the kth ancestor of any node in a tree using efficient binary-tree traversal and dynamic state tracking methods.

binary search dynamic programming tree depth first search breadth first search

Problem Statement

Given a tree with n nodes labeled from 0 to n - 1, represented as an array parent where parent[i] is the parent of node i, and parent[0] = -1 indicating the root, implement a system to find ancestors efficiently. The tree structure requires handling multiple queries for any node's kth ancestor.

Design the TreeAncestor class with a constructor TreeAncestor(n, parent) and a method getKthAncestor(node, k) that returns the kth ancestor of the given node. If the kth ancestor does not exist, return -1. Queries must be answered efficiently to avoid time limit exceeded issues in large trees.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["TreeAncestor", "getKthAncestor", "getKthAncestor", "getKthAncestor"] [[7, [-1, 0, 0, 1, 1, 2, 2]], [3, 1], [5, 2], [6, 3]] Output [null, 1, 0, -1]

Explanation TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]); treeAncestor.getKthAncestor(3, 1); // returns 1 which is the parent of 3 treeAncestor.getKthAncestor(5, 2); // returns 0 which is the grandparent of 5 treeAncestor.getKthAncestor(6, 3); // returns -1 because there is no such ancestor

Constraints

1 <= k <= n <= 5 * 104
parent.length == n
parent[0] == -1
0 <= parent[i] < n for all 0 < i < n
0 <= node < n
There will be at most 5 * 104 queries.

Solution Approach

Precompute ancestors using Binary Lifting

Construct a DP table where dp[i][j] stores the 2^j-th ancestor of node i. This allows any kth ancestor query to be broken into O(log k) steps using powers of two. This approach directly addresses the problem's need for fast repeated ancestor lookups.

Handle queries efficiently

For getKthAncestor(node, k), iterate through the binary representation of k and move up the DP table accordingly. Each bit indicates a jump in the precomputed table. This ensures that each query runs in logarithmic time, preventing time limit exceeded errors.

Manage edge cases carefully

If a node does not have a kth ancestor, return -1 immediately. Initialize the DP table with -1 for nodes without sufficient ancestors. This avoids incorrect lookups and ensures the solution works for nodes close to the root.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Preprocessing with binary lifting takes O(n log n) time and space for the DP table. Each getKthAncestor query is answered in O(log k) time, which is crucial to meet the problem constraints of up to 5 * 10^4 queries efficiently.

What Interviewers Usually Probe

Check if the candidate uses binary lifting or another logarithmic ancestor retrieval method.
Listen for explanations on how state propagation in the tree avoids redundant traversal.
Watch for awareness of edge cases when k exceeds the node's depth.

Common Pitfalls or Variants

Common pitfalls

Attempting to traverse up k steps linearly for each query, causing time limit exceeded errors.
Not initializing ancestor table correctly, leading to incorrect returns for nodes near the root.
Ignoring the binary representation approach, missing the opportunity for logarithmic query optimization.

Follow-up variants

Compute the lowest common ancestor (LCA) for multiple pairs of nodes using similar binary lifting preprocessing.
Determine the distance between any two nodes efficiently using ancestor jumps.
Support dynamic tree modifications with online ancestor queries, requiring updated state propagation.

FAQ

What is the primary technique for fast kth ancestor queries in this problem?

Binary lifting with a DP table of 2^j-th ancestors enables each query to execute in O(log k) time.

Can getKthAncestor return -1?

Yes, if the node does not have a kth ancestor, the method should return -1 immediately.

What is the space complexity of precomputing ancestors?

Storing the DP table for all nodes and all powers of two ancestors requires O(n log n) space.

How does GhostInterview help with large numbers of queries?

It ensures all queries use precomputed states, avoiding linear traversal and time limit exceeded errors.

Is binary-tree traversal always necessary in this problem?

Traversal is needed initially to build ancestor relationships, but subsequent queries rely on precomputed jumps rather than repeated traversal.

terminal

Solution

Solution 1: Dynamic Programming + Binary Lifting

The problem asks us to find the $k$-th ancestor node of a node $node$. If we solve it by brute force, we need to traverse upwards from $node$ for $k$ times, which has a time complexity of $O(k)$ and will obviously exceed the time limit.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class TreeAncestor:
    def __init__(self, n: int, parent: List[int]):
        self.p = [[-1] * 18 for _ in range(n)]
        for i, fa in enumerate(parent):
            self.p[i][0] = fa
        for j in range(1, 18):
            for i in range(n):
                if self.p[i][j - 1] == -1:
                    continue
                self.p[i][j] = self.p[self.p[i][j - 1]][j - 1]

    def getKthAncestor(self, node: int, k: int) -> int:
        for i in range(17, -1, -1):
            if k >> i & 1:
                node = self.p[node][i]
                if node == -1:
                    break
        return node


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

Continue Practicing

#1261 find elements in a contaminated binary tree #1993 operations on tree #1457 pseudo palindromic paths in a binary tree