Is Kth Ancestor of a Tree Node easy or hard?

Kth Ancestor of a Tree Node is categorized as a Hard problem because it requires preprocessing techniques like Binary Lifting and careful handling of tree ancestor relationships. The difficulty comes from designing a data structure that supports fast repeated queries.

Kth Ancestor of a Tree Node Python or Java solution

Python implementations usually store the ancestor table in a list of lists and process bits of k during queries. Java solutions use a 2D array for the jump table and iterate through powers of two. Both implementations follow the same Binary Lifting logic with O(log n) query time.

How to solve Kth Ancestor of a Tree Node in O(log n)?

Use Binary Lifting. Build a table where up[node][j] stores the 2^j-th ancestor. For a query (node, k), examine the binary representation of k and jump using the corresponding powers of two. Each jump is constant time, resulting in O(log n) query complexity.

What is the best approach for Kth Ancestor of a Tree Node?

Binary Lifting is the optimal approach. It precomputes 2^j ancestors for every node so queries can jump upward in logarithmic steps. After O(n log n) preprocessing, each query runs in O(log n) time using simple table lookups.

Is Kth Ancestor of a Tree Node asked at Google/Amazon/Meta?

Ancestor queries on trees and Binary Lifting techniques appear in interviews at companies like Google, Amazon, and Meta. Variations include Lowest Common Ancestor (LCA), k-th ancestor queries, and tree preprocessing problems that test advanced tree algorithms.

What data structure is used in Kth Ancestor of a Tree Node?

The main structure is a 2D ancestor table used for Binary Lifting. Each entry stores the 2^j-th ancestor of a node. The tree itself is typically represented using a parent array or adjacency list built with DFS or BFS.

What is the time complexity of Kth Ancestor of a Tree Node?

The naive approach takes O(k) time per query by walking up the parent chain. The optimized Binary Lifting solution performs O(n log n) preprocessing and answers each query in O(log n) time, which is efficient for large numbers of queries.

Description Hints 2 Solution Video 18:01

1483. Kth Ancestor of a Tree Node

Hard39.7% acceptance3 companies

You are given a tree with n nodes numbered from 0 to n - 1 in the form of a parent array parent where parent[i] is the parent of i^th node. The root of the tree is node 0. Find the k^th ancestor of a given node.

The k^th ancestor of a tree node is the k^th node in the path from that node to the root node.

Implement the TreeAncestor class:

TreeAncestor(int n, int[] parent) Initializes the object with the number of nodes in the tree and the parent array.
int getKthAncestor(int node, int k) return the k^th ancestor of the given node node. If there is no such ancestor, return -1.

Example 1:

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 * 10⁴
parent.length == n
parent[0] == -1
0 <= parent[i] < n for all 0 < i < n
0 <= node < n
There will be at most 5 * 10⁴ queries.

Asked at 3 companies

Google Goldman Sachs Amazon

Topics

Hints open one at a time

Hint 1

The queries must be answered efficiently to avoid time limit exceeded verdict.

Hint 2

Use sparse table (dynamic programming application) to travel the tree upwards in a fast way.

18:01

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution