1483. Kth Ancestor of a Tree Node LeetCode Solution

In this guide, you will get 1483. Kth Ancestor of a Tree Node LeetCode Solution with the best time and space complexity. The solution to Kth Ancestor of a Tree Node problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Kth Ancestor of a Tree Node solution in C++
Kth Ancestor of a Tree Node solution in Java
Kth Ancestor of a Tree Node solution in Python
Additional Resources

1483. Kth Ancestor of a Tree Node LeetCode Solution image

Problem Statement of Kth Ancestor of a Tree Node

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 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.
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 kth 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 * 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.

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n\log n)

1483. Kth Ancestor of a Tree Node LeetCode Solution in C++

class TreeAncestor {
 public:
  TreeAncestor(int n, vector<int>& parent)
      : maxLevel(32 - __builtin_clz(n)), dp(n, vector<int>(maxLevel)) {
    // Node i's 2^0 ancestor is its direct parent.
    for (int i = 0; i < n; ++i)
      dp[i][0] = parent[i];

    for (int j = 1; j < maxLevel; ++j)
      for (int i = 0; i < n; ++i)
        if (dp[i][j - 1] == -1)  // There's no such ancestor.
          dp[i][j] = -1;
        else  // A(i, 2^j) = A(A(i, 2^{j - 1}), 2^{j - 1})
          dp[i][j] = dp[dp[i][j - 1]][j - 1];
  }

  int getKthAncestor(int node, int k) {
    for (int j = 0; j < maxLevel && node != -1; ++j)
      if (k >> j & 1)
        node = dp[node][j];
    return node;
  }

 private:
  const int maxLevel;
  vector<vector<int>> dp;  // dp[i][j] := node i's 2^j-th ancestor
};
/* code provided by PROGIEZ */

1483. Kth Ancestor of a Tree Node LeetCode Solution in Java

class TreeAncestor {
  public TreeAncestor(int n, int[] parent) {
    this.maxLevel = 32 - Integer.numberOfLeadingZeros(n);
    this.dp = new int[n][maxLevel];

    // Node i's 2^0 ancestor is its direct parent.
    for (int i = 0; i < n; ++i)
      dp[i][0] = parent[i];

    for (int j = 1; j < maxLevel; ++j)
      for (int i = 0; i < n; ++i)
        if (dp[i][j - 1] == -1) // There's no such ancestor.
          dp[i][j] = -1;
        else // A(i, 2^j) = A(A(i, 2^{j - 1}), 2^{j - 1})
          dp[i][j] = dp[dp[i][j - 1]][j - 1];
  }

  public int getKthAncestor(int node, int k) {
    for (int j = 0; j < maxLevel && node != -1; ++j)
      if ((k >> j & 1) == 1)
        node = dp[node][j];
    return node;
  }

  private final int maxLevel;
  private int[][] dp; // dp[i][j] := node i's 2^j-th ancestor
}
// code provided by PROGIEZ

1483. Kth Ancestor of a Tree Node LeetCode Solution in Python

class TreeAncestor:
  def __init__(self, n: int, parent: list[int]):
    self.maxLevel = n.bit_length()
    # dp[i][j] := node i's 2^j-th ancestor
    self.dp = [[0] * self.maxLevel for _ in range(n)]

    # Node i's 2^0 ancestor is its direct parent
    for i in range(n):
      self.dp[i][0] = parent[i]

    for j in range(1, self.maxLevel):
      for i in range(n):
        if self.dp[i][j - 1] == -1:  # There's no such ancestor
          self.dp[i][j] = -1
        else:  # A(i, 2^j) = A(A(i, 2^{j - 1}), 2^{j - 1})
          self.dp[i][j] = self.dp[self.dp[i][j - 1]][j - 1]

  def getKthAncestor(self, node: int, k: int) -> int:
    for j in range(self.maxLevel):
      if node == -1:
        break
      if k >> j & 1:
        node = self.dp[node][j]
    return node
 # code by PROGIEZ