Kth Ancestor of a Tree Node - Practice Coding Problems

Kth Ancestor of a Tree Node - Problem

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

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 the i^th node. The root of the tree is node 0. Find the k^th ancestor of a given node.

The k^th ancestor of a tree node is the k^th 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) - Returns the k^th ancestor of the given node. If there is no such ancestor, return -1.

Input & Output

Example 1 — Basic Ancestor Query

$ Input: n = 7, parent = [-1,0,0,1,1,2,2], operations = [[3,1],[5,2],[6,3]]

› Output: [1,0,0]

💡 Note: TreeAncestor(7, [-1,0,0,1,1,2,2]) creates the tree. getKthAncestor(3,1) returns 1 (parent of 3), getKthAncestor(5,2) returns 0 (grandparent of 5), getKthAncestor(6,3) returns 0 (great-grandparent of 6)

Example 2 — No Such Ancestor

$ Input: n = 5, parent = [-1,0,0,1,2], operations = [[4,3],[2,4]]

› Output: [-1,-1]

💡 Note: Node 4's path to root is 4→2→0 (only 2 ancestors), so 3rd ancestor doesn't exist. Node 2's path is 2→0 (only 1 ancestor), so 4th ancestor doesn't exist

Example 3 — Root Ancestor Query

$ Input: n = 3, parent = [-1,0,1], operations = [[2,1],[2,2],[0,1]]

› Output: [1,0,-1]

💡 Note: getKthAncestor(2,1) = 1 (parent of 2), getKthAncestor(2,2) = 0 (grandparent of 2), getKthAncestor(0,1) = -1 (root has no parent)

Constraints

1 ≤ n ≤ 5 × 10⁴
parent[0] == -1
0 ≤ parent[i] < n for i > 0
1 ≤ k ≤ 5 × 10⁴
At most 5 × 10⁴ queries

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Tree with parent array [-1,0,0,1,1,2,2]

Query Processing

Find kth ancestor using binary lifting

Output

Return ancestor node or -1 if not found

Key Takeaway

🎯 Key Insight: Binary lifting precomputes 2^i ancestors to answer any kth ancestor query in logarithmic time

Asked in

G Google 28 f Facebook 15 a Amazon 12

The key insight is to use binary lifting to precompute ancestors at exponential distances (2^0, 2^1, 2^2, ...). This allows any kth ancestor query to be answered in O(log k) time by decomposing k into its binary representation. Best approach is binary lifting with Time: O(log k) per query, Space: O(n log n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Direct Parent Traversal	O(k)	O(n)	For each query, traverse k steps up the tree one parent at a time
Binary Lifting - Precompute Jump Table	O(log k)	O(n log n)	Precompute ancestors at distances 2^0, 2^1, 2^2, ... to jump in O(log k) time

Brute Force - Direct Parent Traversal — Algorithm Steps

Store parent array during initialization
For each query, start at given node
Follow parent pointers k times
Return final node or -1 if path is too short

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin at target node

Traverse

Follow parent pointers k times

Result

Return final node or -1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* parent;
    int n;
} TreeAncestor;

TreeAncestor* treeAncestorCreate(int n, int* parent) {
    TreeAncestor* obj = (TreeAncestor*)malloc(sizeof(TreeAncestor));
    obj->parent = (int*)malloc(n * sizeof(int));
    obj->n = n;
    for (int i = 0; i < n; i++) {
        obj->parent[i] = parent[i];
    }
    return obj;
}

int treeAncestorGetKthAncestor(TreeAncestor* obj, int node, int k) {
    int current = node;
    for (int i = 0; i < k; i++) {
        if (current == -1) return -1;
        current = obj->parent[current];
    }
    return current;
}

void treeAncestorFree(TreeAncestor* obj) {
    free(obj->parent);
    free(obj);
}

int main() {
    int n;
    scanf("%d", &n);
    
    int* parent = (int*)malloc(n * sizeof(int));
    char line[10000];
    getchar();
    fgets(line, sizeof(line), stdin);
    
    // Parse parent array
    char* ptr = line + 1; // skip '['
    for (int i = 0; i < n; i++) {
        parent[i] = strtol(ptr, &ptr, 10);
        if (*ptr == ',') ptr++;
    }
    
    // Parse operations
    fgets(line, sizeof(line), stdin);
    int opCount = 0;
    int operations[1000][2];
    ptr = line + 1; // skip '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            operations[opCount][0] = strtol(ptr, &ptr, 10);
            if (*ptr == ',') ptr++;
            operations[opCount][1] = strtol(ptr, &ptr, 10);
            opCount++;
        }
        ptr++;
    }
    
    TreeAncestor* tree = treeAncestorCreate(n, parent);
    printf("[");
    for (int i = 0; i < opCount; i++) {
        int result = treeAncestorGetKthAncestor(tree, operations[i][0], operations[i][1]);
        printf("%d", result);
        if (i < opCount - 1) printf(",");
    }
    printf("]\n");
    
    treeAncestorFree(tree);
    free(parent);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k)

Each query requires traversing k parent links in worst case

✓ Linear Growth

Space Complexity

O(n)

Only store the parent array of size n

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Direct Parent Traversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler