ProgramGuru

Find the kth Ancestor of a Node in a Binary Tree

Problem and examples

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.

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

How it works

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.

  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).

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v): val(v), left(nullptr), right(nullptr) {}
};

class AncestorFinder {
    TreeNode* result = nullptr;
    int k;
public:
    TreeNode* findKthAncestor(TreeNode* root, int target, int kVal) {
        k = kVal;
        find(root, target);
        return result;
    }
private:
    bool find(TreeNode* node, int target) {
        if (!node) return false;
        if (node->val == target) return true;
        if (find(node->left, target) || find(node->right, target)) {
            if (--k == 0) result = node;
            return true;
        }
        return false;
    }
};

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

    AncestorFinder af;
    TreeNode* ancestor = af.findKthAncestor(root, 5, 2);
    if (ancestor)
        cout << "The kth ancestor is: " << ancestor->val << endl;
    else
        cout << "No kth ancestor found." << endl;
    return 0;
}

Python implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kthAncestor(root, target, k):
    def helper(node, target, k):
        if not node:
            return None, k
        if node.val == target:
            return node, k
        left_node, left_k = helper(node.left, target, k)
        if left_node:
            left_k -= 1
            if left_k == 0:
                return node, 0
            return left_node, left_k
        right_node, right_k = helper(node.right, target, k)
        if right_node:
            right_k -= 1
            if right_k == 0:
                return node, 0
            return right_node, right_k
        return None, k
    node, rem = helper(root, target, k)
    return node if rem == 0 else None

if __name__ == '__main__':
    root = TreeNode(1,
                    TreeNode(2, TreeNode(4), TreeNode(5)),
                    TreeNode(3))
    ancestor = kthAncestor(root, 5, 2)
    print("The kth ancestor is:", ancestor.val if ancestor else "None")

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class KthAncestorFinder {
    private TreeNode result;
    private int k;

    public TreeNode find(TreeNode root, int target, int kVal) {
        this.k = kVal;
        helper(root, target);
        return result;
    }

    private boolean helper(TreeNode node, int target) {
        if (node == null) return false;
        if (node.val == target) return true;
        if (helper(node.left, target) || helper(node.right, target)) {
            if (--k == 0) result = node;
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        KthAncestorFinder finder = new KthAncestorFinder();
        TreeNode ancestor = finder.find(root, 5, 2);
        if (ancestor != null)
            System.out.println("The kth ancestor is: " + ancestor.val);
        else
            System.out.println("No kth ancestor found.");
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function findKthAncestor(root, target, k) {
    let ancestor = null;
    function dfs(node) {
        if (!node) return false;
        if (node.val === target) return true;
        if (dfs(node.left) || dfs(node.right)) {
            k--;
            if (k === 0) ancestor = node;
            return true;
        }
        return false;
    }
    dfs(root);
    return ancestor;
}

const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), new TreeNode(5)),
    new TreeNode(3));

const ancestor = findKthAncestor(root, 5, 2);
console.log(ancestor ? `The kth ancestor is: ${ancestor.val}` : "No kth ancestor found.");

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

var ancestor *TreeNode
var k int

func findKthAncestor(root *TreeNode, target int, kVal int) *TreeNode {
    ancestor = nil
    k = kVal
    helper(root, target)
    return ancestor
}

func helper(node *TreeNode, target int) bool {
    if node == nil {
        return false
    }
    if node.val == target {
        return true
    }
    if helper(node.left, target) || helper(node.right, target) {
        k--
        if k == 0 {
            ancestor = node
        }
        return true
    }
    return false
}

func main() {
    root := &TreeNode{1, &TreeNode{2, &TreeNode{4, nil, nil}, &TreeNode{5, nil, nil}}, &TreeNode{3, nil, nil}}
    result := findKthAncestor(root, 5, 2)
    if result != nil {
        fmt.Println("The kth ancestor is:", result.val)
    } else {
        fmt.Println("No kth ancestor found.")
    }
}

Rust implementation

use std::rc::Rc;
use std::cell::RefCell;

type NodeRef = Rc<RefCell<TreeNode>>;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<NodeRef>,
    right: Option<NodeRef>,
}

fn find_kth_ancestor(root: Option<NodeRef>, target: i32, k: &mut i32, res: &mut Option<NodeRef>) -> bool {
    if root.is_none() {
        return false;
    }
    let node = root.as_ref().unwrap();
    if node.borrow().val == target {
        return true;
    }
    if find_kth_ancestor(node.borrow().left.clone(), target, k, res)
        || find_kth_ancestor(node.borrow().right.clone(), target, k, res) {
        *k -= 1;
        if *k == 0 {
            *res = Some(Rc::clone(node));
        }
        return true;
    }
    false
}

fn main() {
    let root = Rc::new(RefCell::new(TreeNode {
        val: 1,
        left: Some(Rc::new(RefCell::new(TreeNode {
            val: 2,
            left: Some(Rc::new(RefCell::new(TreeNode { val: 4, left: None, right: None }))),
            right: Some(Rc::new(RefCell::new(TreeNode { val: 5, left: None, right: None })))
        }))),
        right: Some(Rc::new(RefCell::new(TreeNode { val: 3, left: None, right: None })))
    }));

    let mut k = 2;
    let mut res = None;
    find_kth_ancestor(Some(root.clone()), 5, &mut k, &mut res);

    if let Some(node) = res {
        println!("The kth ancestor is: {}", node.borrow().val);
    } else {
        println!("No kth ancestor found.");
    }
}

Kotlin implementation

class TreeNode(val value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

var result: TreeNode? = null
var kVal: Int = 0

fun findKthAncestor(root: TreeNode?, target: Int, k: Int): TreeNode? {
    kVal = k
    dfs(root, target)
    return result
}

fun dfs(node: TreeNode?, target: Int): Boolean {
    if (node == null) return false
    if (node.value == target) return true
    if (dfs(node.left, target) || dfs(node.right, target)) {
        kVal--
        if (kVal == 0) result = node
        return true
    }
    return false
}

fun main() {
    val root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left?.left = TreeNode(4)
    root.left?.right = TreeNode(5)

    val ancestor = findKthAncestor(root, 5, 2)
    println("The kth ancestor is: ${ancestor?.value ?: "None"}")
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
        self.val = val
        self.left = left
        self.right = right
    }
}

var kthAncestor: TreeNode? = nil
var k = 0

func findKthAncestor(_ root: TreeNode?, _ target: Int, _ kVal: Int) -> TreeNode? {
    k = kVal
    _ = dfs(root, target)
    return kthAncestor
}

func dfs(_ node: TreeNode?, _ target: Int) -> Bool {
    guard let node = node else { return false }
    if node.val == target { return true }
    if dfs(node.left, target) || dfs(node.right, target) {
        k -= 1
        if k == 0 { kthAncestor = node }
        return true
    }
    return false
}

let root = TreeNode(1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3))

if let ancestor = findKthAncestor(root, 5, 2) {
    print("The kth ancestor is: \(ancestor.val)")
} else {
    print("No kth ancestor found.")
}

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

let k: number;
let result: TreeNode | null = null;

function findKthAncestor(root: TreeNode | null, target: number, kVal: number): TreeNode | null {
    k = kVal;
    dfs(root, target);
    return result;
}

function dfs(node: TreeNode | null, target: number): boolean {
    if (!node) return false;
    if (node.val === target) return true;
    if (dfs(node.left, target) || dfs(node.right, target)) {
        k--;
        if (k === 0) result = node;
        return true;
    }
    return false;
}

const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), new TreeNode(5)),
    new TreeNode(3)
);

const ancestor = findKthAncestor(root, 5, 2);
console.log(ancestor ? `The kth ancestor is: ${ancestor.val}` : "No kth ancestor found.");