এই সমস্যায়, আমাদের একটি বাইনারি ট্রি এবং একটি পূর্ণসংখ্যা N দেওয়া আছে। কাজ হল বাইনারি ট্রির প্রি-অর্ডার ট্রাভার্সেলে n-তম নোড খুঁজে বের করা।
বাইনারি ট্রিতে প্রতিটি নোডের সর্বোচ্চ দুটি চাইল্ড হতে পারে।
ট্রাভার্সেল হল একটি প্রসেস যা ট্রির সব নোড ভিজিট করে এবং তাদের মান প্রিন্ট করতে পারে।
উদাহরণ
ইনপুট
N = 6
আউটপুট
6
ব্যাখ্যা
ট্রির প্রি-অর্ডার ট্রাভার্সেল: 1, 2, 4, 5, 3, 6, 7
সমাধানের পদ্ধতি
আইডিয়া হল বাইনারি ট্রির প্রি-অর্ডার ট্রাভার্সেল ব্যবহার করা যা রিকারসিভ কল দিয়ে করা হয়। প্রতিটি কলেই আমরা রুট নোড ভিজিট করব, তারপর বাম সাবট্রির জন্য preOrder() কল করব, এবং তারপর ডান সাবট্রির জন্য preOrder() কল করব। এই ট্রাভার্সেলের সময় নোড কাউন্ট করব এবং যেটির কাউন্ট N, সেই নোড প্রিন্ট করব।
প্রোগ্রাম উদাহরণ
#include <iostream>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
struct Node* createNode(int item) {
Node* temp = new Node;
temp->data = item;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void findPreOrderTraversalRec(struct Node* root, int N) {
static int nodeCount = 0;
if (root == NULL)
return;
if (nodeCount <= N) {
nodeCount++;
if (nodeCount == N)
cout << root->data;
findPreOrderTraversalRec(root->left, N);
findPreOrderTraversalRec(root->right, N);
}
}
int main() {
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
int N = 6;
cout << N << "th node in preorder traversal is ";
findPreOrderTraversalRec(root, N);
return 0;
}
আউটপুট
6th node in preorder traversal is 6
