text: Kth ancestor of all nodes in an N | C ++ implementation of the above approach ; Function to add an edge in the tree ; DFS to find the Kth ancestor of every node ; Pushing current node in the vector ; Traverse its neighbors ; If K ancestors are not found for current node ; Add the Kth ancestor for the node ; Function to find Kth ancestor of each node ; Building the tree ; Stores all parents of a node ; Store Kth ancestor of all nodes ; Print the ancestors ; Driver Code ; Given N and K ; Given edges of n - ary tree ; Function Call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void addEdge ( vector < int > v [ ] , int x , int y ) { v [ x ] . push_back ( y ) ; v [ y ] . push_back ( x ) ; } void dfs ( vector < int > tree [ ] , vector < int > & temp , int ancestor [ ] , int u , int parent , int k ) { temp . push_back ( u ) ; for ( auto i : tree [ u ] ) { if ( i == parent ) continue ; dfs ( tree , temp , ancestor , i , u , k ) ; } temp . pop_back ( ) ; if ( temp . size ( ) < k ) { ancestor [ u ] = -1 ; } else { ancestor [ u ] = temp [ temp . size ( ) - k ] ; } } void KthAncestor ( int N , int K , int E , int edges [ ] [ 2 ] ) { vector < int > tree [ N + 1 ] ; for ( int i = 0 ; i < E ; i ++ ) { addEdge ( tree , edges [ i ] [ 0 ] , edges [ i ] [ 1 ] ) ; } vector < int > temp ; int ancestor [ N + 1 ] ; dfs ( tree , temp , ancestor , 1 , 0 , K ) ; for ( int i = 1 ; i <= N ; i ++ ) { cout << ancestor [ i ] << " ▁ " ; } } int main ( ) { int N = 9 ; int K = 2 ; int E = 8 ; int edges [ 8 ] [ 2 ] = { { 1 , 2 } , { 1 , 3 } , { 2 , 4 } , { 2 , 5 } , { 2 , 6 } , { 3 , 7 } , { 3 , 8 } , { 3 , 9 } } ; KthAncestor ( N , K , E , edges ) ; return 0 ; }