Binary Trees: Kth Ancestor of a Tree Node

Problem Statement:

You are given a binary tree, a node and an integer “k”.

You need to return the kth ancestor of that node.

Example

The 2nd ancestor of node 4 is node 1.

Solution

We will use DFS in this approach.

We will find the given node in the tree.

Then we backtrack to reach the kth ancestor and then print the node.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <list> 

using namespace std;

struct Node
{
    int data;
    struct Node *left, *right;
};
 
Node* temp = NULL;
 
Node* get_kth_ancestor_DFS(Node *root, int node , int &k)
{  
    if (!root)
        return NULL;
     
    if (root->data == node||
       (temp =  get_kth_ancestor_DFS(root->left,node,k)) ||
       (temp =  get_kth_ancestor_DFS(root->right,node,k)))
    {  
        if (k > 0)       
            --k;
         
        else if (k == 0)
        {
            cout<<"Kth ancestor is: "<<root->data<<endl;
             
            return NULL;
        }
         
        return root;
    }
    return NULL;
}
 
Node* newNode(int data)
{
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
 
int main()
{
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
 
    int k = 2;
    int node = 5;
 
    Node* parent = get_kth_ancestor_DFS(root,node,k);
     

    if (parent)
        cout<<"Kth ancestor is: " << "-1"<<endl;
     
    return 0;
}

Output:

Kth ancestor is: 1