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

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❯

Case 1: Target node has at least k ancestors

This is the normal case. For example, in a tree like: 

              1
             / \
            2   3
           / \
          4   5
If the target node is 5 and k = 2, then we trace back from 5 to 2 (its parent), and from 2 to 1 (its parent). Since k = 2, we return 1 as the 2nd ancestor.

Case 2: Target node exists but has fewer than k ancestors

Consider a tree: 

              1
             / \
            2   3
               /
              4
If the target node is 4 and k = 3, we move from 4 to 3 (1st ancestor), then from 3 to 1 (2nd ancestor). There is no 3rd ancestor, so the result is null.

Case 3: Target node is the root

In this case, the root node doesn’t have any ancestors. For example, if the tree is: 

              1
And the target node is 1 with any k ≥ 1, the output will be null as the root has no ancestors.

Case 4: Deep ancestor with valid k

If the tree is skewed: 

              1
             /
            2
           /
          3
And the target node is 3 with k = 2, we move from 3 to 2 (1st ancestor) and from 2 to 1 (2nd ancestor). So, the output is 1.

Case 5: Empty tree

If the tree is empty, there are no nodes at all. So for any target node and value of k, the answer will always be null.

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

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
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):
    # Helper function that returns a tuple: (found_node, remaining_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 is not None:
            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 is not None:
            right_k -= 1
            if right_k == 0:
                return node, 0
            return right_node, right_k
        return None, k
    
    node, remaining = helper(root, target, k)
    if node is None or remaining != 0:
        return None
    else:
        return node

# Example usage:
if __name__ == '__main__':
    # Construct binary tree:
    #         1
    #        / \
    #       2   3
    #      / \
    #     4   5
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    ancestor = kthAncestor(root, 5, 2)
    if ancestor:
        print('The kth ancestor is:', ancestor.val)
    else:
        print('No kth ancestor found.')