Kth ancestor of all nodes in an N | Java 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
import java . util . * ; class GFG { static void addEdge ( Vector < Integer > v [ ] , int x , int y ) { v [ x ] . add ( y ) ; v [ y ] . add ( x ) ; } static void dfs ( Vector < Integer > tree [ ] , Vector < Integer > temp , int ancestor [ ] , int u , int parent , int k ) { temp . add ( u ) ; for ( int i : tree [ u ] ) { if ( i == parent ) continue ; dfs ( tree , temp , ancestor , i , u , k ) ; } temp . remove ( temp . size ( ) - 1 ) ; if ( temp . size ( ) < k ) { ancestor [ u ] = - 1 ; } else { ancestor [ u ] = temp . get ( temp . size ( ) - k ) ; } } static void KthAncestor ( int N , int K , int E , int edges [ ] [ ] ) { @ SuppressWarnings ( " unchecked " ) Vector < Integer > [ ] tree = new Vector [ N + 1 ] ; for ( int i = 0 ; i < tree . length ; i ++ ) tree [ i ] = new Vector < Integer > ( ) ; for ( int i = 0 ; i < E ; i ++ ) { addEdge ( tree , edges [ i ] [ 0 ] , edges [ i ] [ 1 ] ) ; } Vector < Integer > temp = new Vector < Integer > ( ) ; int [ ] ancestor = new int [ N + 1 ] ; dfs ( tree , temp , ancestor , 1 , 0 , K ) ; for ( int i = 1 ; i <= N ; i ++ ) { System . out . print ( ancestor [ i ] + " ▁ " ) ; } } public static void main ( String [ ] args ) { int N = 9 ; int K = 2 ; int E = 8 ; int edges [ ] [ ] = { { 1 , 2 } , { 1 , 3 } , { 2 , 4 } , { 2 , 5 } , { 2 , 6 } , { 3 , 7 } , { 3 , 8 } , { 3 , 9 } } ; KthAncestor ( N , K , E , edges ) ; } }