Tutorialspoint.dev

Kth ancestor of a node in binary tree | Set 2

Given a binary tree in which nodes are numbered from 1 to n. Given a node and a positive integer K. We have to print the Kth ancestor of the given node in the binary tree. If there does not exist any such ancestor then print -1.

For example in the below given binary tree, 2nd ancestor of node 4 and 5 is 1. 3rd ancestor of node 4 will be -1.



We have discussed a BFS based solution for this problem in our previous article. If you observe that solution carefully, you will see that the basic approach was to first find the node and then backtrack to the kth parent. The same thing can be done using recursive DFS without using an extra array.
The idea of using DFS is to first find the given node in the tree, and then backtrack k times to reach to kth ancestor, once we have reached to the kth parent, we will simply print the node and return NULL.

Below is the implementation of above idea:

C++

/* C++ program to calculate Kth ancestor of given node */
#include <iostream>
#include <queue>
using namespace std;
  
// A Binary Tree Node
struct Node
{
    int data;
    struct Node *left, *right;
};
  
// temporary node to keep track of Node returned
// from previous recursive call during backtrack
Node* temp = NULL;
  
// recursive function to calculate Kth ancestor
Node* kthAncestorDFS(Node *root, int node , int &k)
{   
    // Base case
    if (!root)
        return NULL;
      
    if (root->data == node||
       (temp =  kthAncestorDFS(root->left,node,k)) ||
       (temp =  kthAncestorDFS(root->right,node,k)))
    {   
        if (k > 0)        
            k--;
          
        else if (k == 0)
        {
            // print the kth ancestor
            cout<<"Kth ancestor is: "<<root->data;
              
            // return NULL to stop further backtracking
            return NULL;
        }
          
        // return current node to previous call
        return root;
    }
  
// Utility function to create a new tree node
Node* newNode(int data)
{
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
  
// Driver program to test above functions
int main()
{
    // Let us create binary tree shown in above diagram
    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;
  
    // print kth ancestor of given node
    Node* parent = kthAncestorDFS(root,node,k);
      
    // check if parent is not NULL, it means
    // there is no Kth ancestor of the node
    if (parent)
        cout << "-1";
      
    return 0;
}

Python3

""" Python3 program to calculate Kth 
    ancestor of given node """
  
# A Binary Tree Node 
# Utility function to create a new tree node 
class newNode: 
  
    # Constructor to create a new node 
    def __init__(self, data): 
        self.data = data 
        self.left = None
        self.right = None
  
# recursive function to calculate 
# Kth ancestor 
def kthAncestorDFS(root, node, k): 
      
    # Base case 
    if (not root):
        return None
      
    if (root.data == node or
       (kthAncestorDFS(root.left, node, k)) or
       (kthAncestorDFS(root.right, node, k))):
          
        if (k[0] > 0):
            k[0] -= 1
          
        elif (k[0] == 0):
              
            # prthe kth ancestor 
            print("Kth ancestor is:", root.data)
              
            # return None to stop further
            # backtracking 
            return None
              
        # return current node to previous call 
        return root
      
# Driver Code
if __name__ == '__main__':
    root = newNode(1
    root.left = newNode(2
    root.right = newNode(3
    root.left.left = newNode(4
    root.left.right = newNode(5
  
    k = [2]
    node = 5
  
    # prkth ancestor of given node 
    parent = kthAncestorDFS(root,node,k) 
      
    # check if parent is not None, it means 
    # there is no Kth ancestor of the node 
    if (parent):
        print("-1")
  
# This code is contributed 
# by SHUBHAMSINGH10

Output:

Kth ancestor is: 1

Time Complexity : O(n), where n is the number of nodes in the binary tree.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter