Kth ancestor of all nodes in an N | 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 ; Given N and K ; Given edges of n - ary tree ; Function call
function addEdge ( v , x , y ) { v [ x ] . push ( y ) ; v [ y ] . push ( x ) ; } function dfs ( tree , temp , ancestor , u , parent , k ) { temp . push ( u ) ; for ( let i = 0 ; i < tree [ u ] . length ; i ++ ) { if ( tree [ u ] [ i ] == parent ) continue ; dfs ( tree , temp , ancestor , tree [ u ] [ i ] , u , k ) ; } temp . pop ( ) ; if ( temp . length < k ) { ancestor [ u ] = - 1 ; } else { ancestor [ u ] = temp [ temp . length - k ] ; } } function KthAncestor ( N , K , E , edges ) { let tree = new Array ( N + 1 ) ; for ( let i = 0 ; i < tree . length ; i ++ ) tree [ i ] = [ ] ; for ( let i = 0 ; i < E ; i ++ ) { addEdge ( tree , edges [ i ] [ 0 ] , edges [ i ] [ 1 ] ) ; } let temp = [ ] ; let ancestor = new Array ( N + 1 ) ; dfs ( tree , temp , ancestor , 1 , 0 , K ) ; for ( let i = 1 ; i <= N ; i ++ ) { document . write ( ancestor [ i ] + " " ) ; } } let N = 9 ; let K = 2 ; let E = 8 ; let edges = [ [ 1 , 2 ] , [ 1 , 3 ] , [ 2 , 4 ] , [ 2 , 5 ] , [ 2 , 6 ] , [ 3 , 7 ] , [ 3 , 8 ] , [ 3 , 9 ] ] ; KthAncestor ( N , K , E , edges ) ;