Find the Kth node in the DFS traversal of a given subtree in a Tree | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100005 NEW_LINE int n ; vector < int > tree [ N ] ; int currentIdx ; vector < int > startIdx , endIdx ; vector < int > p ; void Add_edge ( int u , int v ) { tree [ u ] . push_back ( v ) ; tree [ v ] . push_back ( u ) ; } void intisalise ( ) { startIdx . resize ( n ) ; endIdx . resize ( n ) ; p . resize ( n ) ; } void Dfs ( int ch , int par ) { p [ currentIdx ] = ch ; startIdx [ ch ] = currentIdx ++ ; for ( auto c : tree [ ch ] ) { if ( c != par ) Dfs ( c , ch ) ; } endIdx [ ch ] = currentIdx - 1 ; } int findNode ( int v , int k ) { k += startIdx [ v ] - 1 ; if ( k <= endIdx [ v ] ) return p [ k ] ; return -1 ; } int main ( ) { n = 9 ; 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 ; cout << findNode ( v , k ) ; return 0 ; }