इस समस्या में, हमें आकार N का एक ट्री, ट्री का एक नोड V और k दिया गया है। हमारा कार्य ट्री में दिए गए उपट्री के DFS ट्रैवर्सल में K-वां नोड ज्ञात करना है।
हमें शीर्ष V से शुरू होने वाले ट्री के DFS ट्रैवर्सल में k-वां नोड ढूंढना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट :

V = 2, k = 3
आउटपुट : 4
व्याख्या −
श्रृंखला है {1, 2, 3, 5, 6, 7} 4वां तत्व 5 है। समाधान दृष्टिकोण
समस्या का एक सरल समाधान नोड V के DFS ट्रैवर्सल को ढूंढना और इससे k-वां मान प्रिंट करना है।
इसके लिए, हम ट्री का DFS ट्रैवर्सल करते हैं और इसे एक वेक्टर में संग्रहीत करते हैं। इस वेक्टर में, हम Vstart और Vend के मान ढूंढेंगे जो ट्री के DFS ट्रैवर्सल की शुरुआत और अंत को चिह्नित करते हैं। फिर इस रेंज में k-वां मान ढूंढें और यदि संभव हो तो प्रिंट करें।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include <bits/stdc++.h> using namespace std; #define N 100005 int n; vector<int> tree[N]; int currentIdx; vector<int> startIdx,endIdx; vector<int> dfsTraversalVector; void insertEdge(int u, int v){ tree[u].push_back(v); tree[v].push_back(u); } void findDfsTraversal(int ch, int par){ dfsTraversalVector[currentIdx] = ch; startIdx[ch] = currentIdx++; for (auto c : tree[ch]) { if (c != par) findDfsTraversal(c, ch); } endIdx[ch] = currentIdx - 1; } int findKNodeDfsV(int v, int k){ k = k + (startIdx[v] - 1); if (k <= endIdx[v]) return dfsTraversalVector[k]; return -1; } int main(){ n = 9; insertEdge(5, 8); insertEdge(5, 2); insertEdge(5, 10); insertEdge(5, 3); insertEdge(2, 6); insertEdge(2, 1); insertEdge(3, 9); insertEdge(6, 1); insertEdge(9, 7); startIdx.resize(n); endIdx.resize(n); dfsTraversalVector.resize(n); findDfsTraversal(5, 0); int v = 2, k = 4; cout<<k<<"-वां नोड DFS ट्रैवर्सल में नोड "<<v<<" का है "<<findKNodeDfsV(v, k); return 0; } आउटपुट
4-वां नोड DFS ट्रैवर्सल में नोड 2 का है 1