Kth ancestor of a tree node

Binary Search Dynamic Programming Bit Manipulation Tree Depth-First Search Breadth-First Search Design

37.2% acceptance

Feb 23, 2026

2076

124

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

pub struct TreeAncestor {
  up: Vec<Vec<i32>>,
}

impl TreeAncestor {
  pub fn new(_n: i32, parent: Vec<i32>) -> Self {
    let n = parent.len();
    let log = 16usize;
    let mut up = vec![vec![-1i32; n]; log];
    up[0] = parent;
    for j in 1..log {
      for i in 0..n {
        let prev = up[j - 1][i];
        if prev != -1 {
          up[j][i] = up[j - 1][prev as usize];
        }
      }
    }
    TreeAncestor { up }
  }

  pub fn get_kth_ancestor(&self, mut node: i32, k: i32) -> i32 {
    for j in 0..self.up.len() {
      if k & (1 << j) != 0 {
        node = self.up[j][node as usize];
        if node == -1 { return -1; }
      }
    }
    node
  }
}