Find the Kth node in the DFS traversal of a given subtree in a Tree | Javascript 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 ; Number of nodes ; Add edges ; Store DFS of 1 st node
let N = 100005 ; let n = 10 ; let tree = [ ] ; let currentIdx = 0 ; let startIdx ; let endIdx ; let p ; function Add_edge ( u , v ) { tree [ u ] . push ( v ) ; tree [ v ] . push ( u ) ; } function intisalise ( ) { startIdx = new Array ( n + 1 ) ; endIdx = new Array ( n + 1 ) ; p = new Array ( n + 1 ) ; for ( let i = 0 ; i < ( n + 1 ) ; i ++ ) { startIdx [ i ] = 0 ; endIdx [ i ] = 0 ; p [ i ] = 0 ; } } function Dfs ( ch , par ) { p [ currentIdx ] = ch ; startIdx [ ch ] = currentIdx ++ ; for ( let c = 0 ; c < tree [ ch ] . length ; c ++ ) { if ( tree [ ch ] != par ) Dfs ( tree [ ch ] , ch ) ; } endIdx [ ch ] = currentIdx - 1 ; } function findNode ( v , k ) { k += startIdx [ v ] - 1 ; if ( k <= endIdx [ v ] ) return p [ k ] ; return - 1 ; } n = 9 ; for ( let i = 0 ; i <= n ; i ++ ) tree . push ( [ ] ) ; 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 ) ; let v = 3 , k = 4 ; document . write ( findNode ( v , k ) ) ;