Find the Kth node in the DFS traversal of a given subtree in a Tree | Python3 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
N = 100005 NEW_LINE n = 10 NEW_LINE tree = [ [ ] for i in range ( N ) ] NEW_LINE static int n ; NEW_LINE static ArrayList tree = new ArrayList ( ) ; NEW_LINE currentIdx = 0 NEW_LINE startIdx = [ 0 for i in range ( n ) ] NEW_LINE endIdx = [ 0 for i in range ( n ) ] NEW_LINE p = [ 0 for i in range ( n ) ] NEW_LINE def Add_edge ( u , v ) : NEW_LINE INDENT tree [ u ] . append ( v ) NEW_LINE tree [ v ] . append ( u ) NEW_LINE DEDENT def intisalise ( ) : NEW_LINE INDENT pass NEW_LINE DEDENT def Dfs ( ch , par ) : NEW_LINE INDENT global currentIdx NEW_LINE p [ currentIdx ] = ch NEW_LINE startIdx [ ch ] = currentIdx NEW_LINE currentIdx += 1 NEW_LINE for c in tree [ ch ] : NEW_LINE INDENT if ( c != par ) : NEW_LINE INDENT Dfs ( c , ch ) NEW_LINE DEDENT DEDENT endIdx [ ch ] = currentIdx - 1 NEW_LINE DEDENT def findNode ( v , k ) : NEW_LINE INDENT k += startIdx [ v ] - 1 NEW_LINE if ( k <= endIdx [ v ] ) : NEW_LINE INDENT return p [ k ] NEW_LINE DEDENT return - 1 NEW_LINE DEDENT n = 9 NEW_LINE Add_edge ( 1 , 2 ) NEW_LINE Add_edge ( 1 , 3 ) NEW_LINE Add_edge ( 1 , 4 ) NEW_LINE Add_edge ( 3 , 5 ) NEW_LINE Add_edge ( 3 , 7 ) NEW_LINE Add_edge ( 5 , 6 ) NEW_LINE Add_edge ( 5 , 8 ) NEW_LINE Add_edge ( 7 , 9 ) NEW_LINE intisalise ( ) NEW_LINE Dfs ( 1 , 0 ) NEW_LINE v , k = 3 , 4 NEW_LINE print ( findNode ( v , k ) ) NEW_LINE