Find the Kth node in the DFS traversal of a given subtree in a Tree
Given a tree with N nodes, and two integers K and V. The task is to find the Kth node in the DFS traversal of the vertex V.
Consider the below Tree:
DFS of node number 1 is [1, 2, 3, 5, 6, 8, 7, 9, 4].
DFS of node number 3 is [3, 5, 6, 8, 7, 9]
DFS of node number 7 is [7, 9]
DFS of node number 9 is [9].
Print “-1” if the numbers in the DFS of vertex V are less than K.
Examples:
Input : Tree: Shown in above image, V = 3, K = 4 Output : 8 Input : Tree: Shown in above image, V = 7, K = 3 Output : -1
Approach : Let’s construct a vector p: to store the DFS traversal of the complete tree from vertex 1. Let tinv be the position of the vertex V in the vector p (the size of the vector p in moment we call DFS from the vertex V) and toutv be the position of the first vertex pushed to the vector after leaving the subtree of vertex V (the size of the vector p in moment when we return from DFS from the vertex V). Then it is obvious that the subtree of the vertex V lies in the interval [tinv, toutv).
So, to find the Kth node in the DFS of the subtree of node V, we will have to return the Kth node in the interval [tinv, toutv).
Below is the implementation of the above approach:
C++
// C++ program to find the Kth node in the// DFS traversal of the subtree of given// vertex V in a Tree#include <bits/stdc++.h>using namespace std;#define N 100005// To store nodesint n;vector<int> tree[N];// To store the current index of vertex in DFSint currentIdx;// To store the starting index and ending// index of vertex in the DFS traversal arrayvector<int> startIdx, endIdx;// To store the DFS of vertex 1vector<int> p;// Function to add edge between two nodesvoid Add_edge(int u, int v){ tree[u].push_back(v); tree[v].push_back(u);}// Initialize the vectorsvoid intisalise(){ startIdx.resize(n); endIdx.resize(n); p.resize(n);}// 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 vertexvoid Dfs(int ch, int par){ p[currentIdx] = ch; // store starting index of node ch startIdx[ch] = currentIdx++; for (auto c : tree[ch]) { if (c != par) Dfs(c, ch); } // store ending index endIdx[ch] = currentIdx - 1;}// Function to find the Kth node in DFS of vertex Vint findNode(int v, int k){ k += startIdx[v] - 1; // check if kth number exits or not if (k <= endIdx[v]) return p[k]; return -1;}// Driver codeint main(){ // number of nodes n = 9; // add edges 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(); // store DFS of 1st node Dfs(1, 0); int v = 3, k = 4; cout << findNode(v, k); return 0;} |
Java
// Java program to find the Kth node in the// DFS traversal of the subtree of given// vertex V in a Treeimport java.util.*;class GFG{ static int N = 100005;// To store nodesstatic int n;static ArrayList< ArrayList<Integer>> tree = new ArrayList<>();// To store the current index of vertex in DFSstatic int currentIdx;// To store the starting index and ending// index of vertex in the DFS traversal arraystatic int[] startIdx;static int[] endIdx;// To store the DFS of vertex 1static int[] p;// Function to add edge between two nodesstatic void Add_edge(int u, int v){ tree.get(u).add(v); tree.get(v).add(u);}// Initialize the vectorsstatic void intisalise(){ startIdx = new int[n + 1]; endIdx = new int[n + 1]; p = new int[n + 1];}// 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 vertexstatic void Dfs(int ch, int par){ p[currentIdx] = ch; // store starting index of node ch startIdx[ch] = currentIdx++; for(int c : tree.get(ch)) { if (c != par) Dfs(c, ch); } // store ending index endIdx[ch] = currentIdx - 1;}// Function to find the Kth node // in DFS of vertex Vstatic int findNode(int v, int k){ k += startIdx[v] - 1; // Check if kth number exits or not if (k <= endIdx[v]) return p[k]; return -1;}// Driver codepublic static void main(String[] args){ // Number of nodes n = 9; for(int i = 0; i <= n; i++) tree.add(new ArrayList<Integer>()); // Add edges 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(); // Store DFS of 1st node Dfs(1, 0); int v = 3, k = 4; System.out.println(findNode(v, k));}}// This code is contributed by jrishabh99 |
Python3
# Python3 program to find the Kth node in the# DFS traversal of the subtree of given# vertex V in a TreeN = 100005n = 10tree = [[]for i in range(N)]# To store the current index of vertex in DFScurrentIdx = 0# To store the starting index and ending# index of vertex in the DFS traversal arraystartIdx = [0 for i in range(n)]endIdx = [0 for i in range(n)]# To store the DFS of vertex 1p = [0 for i in range(n)]# Function to add edge between two nodesdef Add_edge(u, v): tree[u].append(v) tree[v].append(u)# Initialize the vectorsdef intisalise(): pass# 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 vertexdef Dfs(ch, par): global currentIdx p[currentIdx] = ch # store starting index of node ch startIdx[ch] = currentIdx currentIdx += 1 for c in tree[ch]: if (c != par): Dfs(c, ch) # store ending index endIdx[ch] = currentIdx - 1# Function to find the Kth node in # DFS of vertex Vdef findNode(v, k): k += startIdx[v] - 1 # check if kth number exits or not if (k <= endIdx[v]): return p[k] return -1# Driver code# number of nodesn = 9# add edgesAdd_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()# store DFS of 1st nodeDfs(1, 0)v, k = 3, 4print(findNode(v, k))# This code is contributed by mohit kumar |
C#
// C# program to find the Kth node in the // DFS traversal of the subtree of given // vertex V in a Tree using System; using System.Collections;using System.Collections.Generic; class GFG{ // To store nodes static int n; static ArrayList tree = new ArrayList(); // To store the current index of vertex in DFS static int currentIdx; // To store the starting index and ending // index of vertex in the DFS traversal array static int[] startIdx; static int[] endIdx; // To store the DFS of vertex 1 static int[] p; // Function to add edge between two nodes static void Add_edge(int u, int v) { ((ArrayList)tree[u]).Add(v); ((ArrayList)tree[v]).Add(u); } // Initialize the vectors static void intisalise() { startIdx = new int[n + 1]; endIdx = new int[n + 1]; p = new int[n + 1]; } // 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 static void Dfs(int ch, int par) { p[currentIdx] = ch; // store starting index of node ch startIdx[ch] = currentIdx++; foreach(int c in (ArrayList)tree[ch]) { if (c != par) Dfs(c, ch); } // store ending index endIdx[ch] = currentIdx - 1; } // Function to find the Kth node // in DFS of vertex V static int findNode(int v, int k) { k += startIdx[v] - 1; // Check if kth number exits or not if (k <= endIdx[v]) return p[k]; return -1; } // Driver code public static void Main(string[] args) { // Number of nodes n = 9; for(int i = 0; i <= n; i++) tree.Add(new ArrayList()); // Add edges 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(); // Store DFS of 1st node Dfs(1, 0); int v = 3, k = 4; Console.Write(findNode(v, k)); } } // This code is contributed by rutvik_56 |
Javascript
<script>// Javascript program to find the Kth node in the// DFS traversal of the subtree of given// vertex V in a Treelet N = 100005;// To store nodeslet n=10;let tree = [];// To store the current index of vertex in DFSlet currentIdx=0;// To store the starting index and ending// index of vertex in the DFS traversal arraylet startIdx;let endIdx;// To store the DFS of vertex 1let p;// Function to add edge between two nodesfunction Add_edge(u,v){ tree[u].push(v); tree[v].push(u);}// Initialize the vectorsfunction 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 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 vertexfunction Dfs(ch,par){ p[currentIdx] = ch; // store starting index of node ch startIdx[ch] = currentIdx++; for(let c=0;c<tree[ch].length;c++) { if (tree[ch] != par) Dfs(tree[ch], ch); } // store ending index endIdx[ch] = currentIdx - 1;}// Function to find the Kth node// in DFS of vertex Vfunction findNode(v,k){ k += startIdx[v] - 1; // Check if kth number exits or not if (k <= endIdx[v]) return p[k]; return -1;}// Driver code// Number of nodes n = 9; for(let i = 0; i <= n; i++) tree.push([]); // Add edges 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(); // Store DFS of 1st node Dfs(1, 0); let v = 3, k = 4; document.write(findNode(v, k));// This code is contributed by unknown2108</script> |
Output:
8
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
