Scale Engineer

Kth Ancestor of a Tree Node

Hard
#1369Time: Constructor: `O(n)` to copy the parent array. `getKthAncestor`: `O(k)` for each query, which is `O(n)` in the worst case. Total for `Q` queries: `O(n + Q * n)`. This is too slow given the constraints and will result in Time Limit Exceeded.Space: `O(n)` to store the parent array.
Patterns
Dynamic ProgrammingDesign
Algorithms
Binary SearchDepth-First SearchBreadth-First Search
Data structures
Tree

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves directly simulating the process of finding an ancestor. To find the k-th ancestor of a node, we simply traverse upwards from the given node towards the root, one step at a time, for k steps.

Algorithm

    1. In the constructor, store the parent array.
    1. In getKthAncestor(node, k), initialize currentNode to node.
    1. Loop k times:
    1. If currentNode is -1, break the loop and return -1.
    1. Update currentNode to parent[currentNode].
    1. After the loop, return currentNode.

Walkthrough

Constructor TreeAncestor(n, parent)

The constructor's role is minimal. It just needs to store the parent array for later use. This can be done by copying the input array into a member variable.

Method getKthAncestor(node, k)

This method implements the upward traversal.

  • It starts with the given node.
  • It then enters a loop that runs k times.
  • In each iteration, it updates the current node to its parent using the stored parent array (node = parent[node]).
  • It also checks if the current node becomes -1. If it does, it means we've reached past the root before completing k steps, so the k-th ancestor does not exist. In this case, we return -1 immediately.
  • If the loop completes without the node becoming -1, the final value of node is the k-th ancestor.
class TreeAncestor {    int[] parent;     public TreeAncestor(int n, int[] parent) {        this.parent = parent;    }     public int getKthAncestor(int node, int k) {        int currentNode = node;        for (int i = 0; i < k; i++) {            if (currentNode == -1) {                return -1;            }            currentNode = this.parent[currentNode];        }        return currentNode;    }}

Complexity

Time

Constructor: `O(n)` to copy the parent array. `getKthAncestor`: `O(k)` for each query, which is `O(n)` in the worst case. Total for `Q` queries: `O(n + Q * n)`. This is too slow given the constraints and will result in Time Limit Exceeded.

Space

`O(n)` to store the parent array.

Trade-offs

Pros

  • Very simple to understand and implement.

  • Low memory usage.

  • Fast constructor.

Cons

  • Inefficient for queries with large k.

  • Fails to pass time limits on platforms like LeetCode for the given constraints.

Solutions

public class TreeAncestor { private int [][] p ; public TreeAncestor ( int n , int [] parent ) { p = new int [ n ][]; for ( int i = 0 ; i < n ; i ++) { p [ i ] = new int [ 18 ]; for ( int j = 0 ; j < 18 ; j ++) { p [ i ][ j ] = - 1 ; } } for ( int i = 0 ; i < n ; ++ i ) { p [ i ][ 0 ] = parent [ i ]; } for ( int j = 1 ; j < 18 ; ++ j ) { for ( int i = 0 ; i < n ; ++ i ) { if ( p [ i ][ j - 1 ] == - 1 ) { continue ; } p [ i ][ j ] = p [ p [ i ][ j - 1 ]][ j - 1 ]; } } } public int GetKthAncestor ( int node , int k ) { for ( int i = 17 ; i >= 0 ; -- i ) { if ((( k >> i ) & 1 ) == 1 ) { node = p [ node ][ i ]; if ( node == - 1 ) { break ; } } } return node ; } } /** * Your TreeAncestor object will be instantiated and called as such: * TreeAncestor obj = new TreeAncestor(n, parent); * int param_1 = obj.GetKthAncestor(node,k); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem