Kth Ancestor Of A Tree Node - Leetcode Solution

The Kth Ancestor Of A Tree Node problem on LeetCode involves finding the kth ancestor of a given node in a tree. The problem statement can be found here: https://leetcode.com/problems/kth-ancestor-of-a-tree-node/

To solve this problem, we can use binary lifting. Binary lifting is a technique that involves precomputing the 2^i-th ancestor of each node, where i is a power of 2. This can be done using dynamic programming.

Let's first define some terms that we will use in the solution:

• Ancestor: A node is an ancestor of another node if it lies on the path from that node to the root.
• Kth Ancestor: The kth ancestor of a node is the parent of the (k-1)th ancestor of the node.

To precompute the 2^i-th ancestor of each node, we can use the recurrence:

P[i][j] = P[i-1][P[i-1][j]]

where P[i][j] represents the 2^i-th ancestor of node j. P[0][j] represents the parent of node j.

We can calculate the P matrix using dynamic programming as follows:

for i in range(1, log2(n)+1): for j in range(1, n+1): P[i][j] = P[i-1][P[i-1][j]]

where log2(n) represents the logarithm base 2 of n.

Once we have precomputed the P matrix, we can find the kth ancestor of a node in O(log k) time using binary lifting:

def find_kth_ancestor(node, k): i = 0 while k > 0: if k % 2 == 1: node = P[i][node] k //= 2 i += 1 return node

We start by setting i=0 and node to the given node. We loop while k is greater than 0. If k is odd, we jump to node's 2^i-th ancestor using the P matrix and subtract 1 from k. Then we divide k by 2 and increment i by 1. We repeat this process until k is 0. The final value of node is the kth ancestor of the given node.

The time complexity of this solution is O(n log n) for precomputation and O(log k) for each query. The space complexity is O(n log n) for the P matrix.

1