We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Kth Ancestor of a Tree Node

Difficulty: Hard

Problem Description

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

Key Insights

  • The tree structure can be represented using a parent array, where each index represents a node and the value at that index represents its parent.
  • To efficiently find the kth ancestor, a binary lifting technique can be utilized, allowing jumps through ancestors in powers of two.
  • This method reduces the time complexity of finding the kth ancestor from O(k) to O(log k).

Space and Time Complexity

Time Complexity: O(log k) for each query due to binary lifting, O(n) for preprocessing. Space Complexity: O(n log n) for storing ancestor information.

Solution

To solve the problem, we will use a data structure to store ancestors at different levels for each node. The approach is to preprocess the parent information into a 2D list where the entry at [i][j] represents the 2^j-th ancestor of node i. For each query, we can then determine the kth ancestor by breaking k down into powers of two and jumping accordingly.

Code Solutions

class TreeAncestor:

    def __init__(self, n: int, parent: List[int]):
        # Initialize a 2D list for ancestors
        self.ancestors = [[-1] * 20 for _ in range(n)]
        for i in range(n):
            self.ancestors[i][0] = parent[i]  # Direct parent

        # Preprocess ancestors for powers of two
        for j in range(1, 20):
            for i in range(n):
                if self.ancestors[i][j - 1] != -1:
                    self.ancestors[i][j] = self.ancestors[self.ancestors[i][j - 1]][j - 1]

    def getKthAncestor(self, node: int, k: int) -> int:
        # Traverse the ancestors using binary lifting
        for j in range(20):
            if k & (1 << j):
                node = self.ancestors[node][j]
                if node == -1:
                    return -1
        return node
← Back to All Questions