Find the kth Ancestor of a Node in a Binary Tree - Algorithm & Code Examples

Binary Trees

Contents

ProblemExamplesSolutionAlgorithmCode

Problem Statement❯

Given a binary tree, a target node value, and an integer k, your task is to find the kth ancestor of the target node. If the node doesn't exist or there are fewer than k ancestors, return null or indicate the absence of such an ancestor.

The tree is not guaranteed to be a Binary Search Tree. The nodes contain unique integer values.

Examples❯

Input Tree Node k k-th Ancestor Description
[1, 2, 3, 4, 5, 6, 7]
7 2 1 7 → parent 3 → parent 1 → 2nd ancestor = 1
[1, 2, 3, null, 4, null, 5]
4 1 2 4 → parent 2 → 1st ancestor = 2
[10, 20, 30, 40, 50, 60, 70]
70 3 10 70 → 30 → 10 → 3rd ancestor = 10
[1, 2, 3, 4, null, null, 5]
5 1 3 5 → parent 3 → 1st ancestor = 3
[1, 2, 3]
3 2 1 3 → 1st ancestor = 1 → 2nd ancestor = root (no further ancestor) = 1
[1, 2, 3, 4, 5, 6, 7]
4 3 -1 4 → 2 → 1 → no ancestor at distance 3 → return -1

Solution❯

Understanding the Problem

We are given a binary tree and a target node. The goal is to find the kth ancestor of this node. An ancestor of a node is any node in the path from the node to the root (excluding the node itself). The 1st ancestor is the parent, the 2nd is the grandparent, and so on.

For example, in the following binary tree: 

    1
   /   2   3
 / 4   5

If the target node is 5 and k = 2, we trace upward: 5 → 2 → 1. So the 2nd ancestor is 1.

Step-by-Step Solution with Example

Step 1: Build a parent map

We first traverse the tree and store each node’s parent in a map. This helps us move upwards from any node without recursion.

Step 2: Start from the target node

Using the parent map, we begin at the target node and move to its parent. We repeat this process k times.

Step 3: Count each jump

Each move upward reduces k by 1. If at any point the parent is null, it means we’ve reached the root or an ancestor doesn’t exist.

Step 4: Return the current node

If after k jumps we’re at a valid node, that’s our answer. Otherwise, return null.

Example Walkthrough

Tree:

    1
   /   2   3
 / 4   5

Target node = 5, k = 2:

  • Start at 5 → parent is 2 → k becomes 1
  • Move to 2 → parent is 1 → k becomes 0

Since k = 0 and we’re at node 1, the answer is 1.

Edge Cases

Case 1: Target node has fewer than k ancestors

Tree: 

    1
   /   2   3
     /
    4
Target node = 4, k = 3
Path: 4 → 3 → 1 → null → k = 0?
Since we ran out of ancestors before reaching k steps, the output is null.

Case 2: Target node is the root

Tree: 

    1
Target node = 1, k ≥ 1
The root has no parent, so any kth ancestor is null.

Case 3: Deep ancestor in a skewed tree

Tree: 

    1
   /
  2
 /
3
Target node = 3, k = 2
Path: 3 → 2 → 1 → Done → Answer is 1.

Case 4: Empty tree

If the tree is empty (i.e., root is null), we cannot find any ancestor. Output is always null.

Finally

This problem teaches us how to think in terms of upward traversal in a tree using parent mapping. It’s essential to handle edge cases like reaching the root too early or when the tree is empty.

A good solution avoids recursion for upward traversal and uses simple loops with a parent map, making it efficient and easy to follow.

Algorithm Steps❯

  1. Given a binary tree, a target node value, and an integer k.
  2. Traverse the tree recursively to find the target node.
  3. While backtracking, decrement k each time an ancestor is visited.
  4. When k reaches 0, the current node is the kth ancestor.
  5. If the target is not found or there is no kth ancestor, return an indication (e.g. null).

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* kthAncestor = NULL;

bool findHelper(TreeNode* root, int target, int* k) {
    if (root == NULL) return false;
    if (root->val == target) return true;
    if (findHelper(root->left, target, k) || findHelper(root->right, target, k)) {
        (*k)--;
        if (*k == 0) {
            kthAncestor = root;
        }
        return true;
    }
    return false;
}

TreeNode* findKthAncestor(TreeNode* root, int target, int k) {
    kthAncestor = NULL;
    findHelper(root, target, &k);
    return kthAncestor;
}

TreeNode* newNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

int main() {
    TreeNode* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    TreeNode* ancestor = findKthAncestor(root, 5, 2);
    if (ancestor)
        printf("The kth ancestor is: %d\n", ancestor->val);
    else
        printf("No kth ancestor found.\n");
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...