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

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