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