Find the Kth node in the DFS traversal of a given subtree in a Tree | Java program to find the Kth node in the DFS traversal of the subtree of given vertex V in a Tree ; To store nodes ; To store the current index of vertex in DFS ; To store the starting index and ending index of vertex in the DFS traversal array ; To store the DFS of vertex 1 ; Function to add edge between two nodes ; Initialize the vectors ; Function to perform DFS of a vertex 1. stores the DFS of the vertex 1 in vector p , 2. store the start index of DFS of every vertex 3. store the end index of DFS of every vertex ; store staring index of node ch ; store ending index ; Function to find the Kth node in DFS of vertex V ; Check if kth number exits or not ; Driver code ; Number of nodes ; Add edges ; Store DFS of 1 st node
import java . util . * ; class GFG { static int N = 100005 ; static int n ; static ArrayList < ArrayList < Integer > > tree = new ArrayList < > ( ) ; static int currentIdx ; static int [ ] startIdx ; static int [ ] endIdx ; static int [ ] p ; static void Add_edge ( int u , int v ) { tree . get ( u ) . add ( v ) ; tree . get ( v ) . add ( u ) ; } static void intisalise ( ) { startIdx = new int [ n + 1 ] ; endIdx = new int [ n + 1 ] ; p = new int [ n + 1 ] ; } static void Dfs ( int ch , int par ) { p [ currentIdx ] = ch ; startIdx [ ch ] = currentIdx ++ ; for ( int c : tree . get ( ch ) ) { if ( c != par ) Dfs ( c , ch ) ; } endIdx [ ch ] = currentIdx - 1 ; } static int findNode ( int v , int k ) { k += startIdx [ v ] - 1 ; if ( k <= endIdx [ v ] ) return p [ k ] ; return - 1 ; } public static void main ( String [ ] args ) { n = 9 ; for ( int i = 0 ; i <= n ; i ++ ) tree . add ( new ArrayList < Integer > ( ) ) ; Add_edge ( 1 , 2 ) ; Add_edge ( 1 , 3 ) ; Add_edge ( 1 , 4 ) ; Add_edge ( 3 , 5 ) ; Add_edge ( 3 , 7 ) ; Add_edge ( 5 , 6 ) ; Add_edge ( 5 , 8 ) ; Add_edge ( 7 , 9 ) ; intisalise ( ) ; Dfs ( 1 , 0 ) ; int v = 3 , k = 4 ; System . out . println ( findNode ( v , k ) ) ; } }