এই সমস্যায়, আমাদের একটি বাইনারি ট্রি এবং একটি পূর্ণসংখ্যা N দেওয়া হয়েছে। কাজটি হল একটি বাইনারি ট্রির প্রি-অর্ডার ট্রাভার্সালে n-ম নোড খুঁজে বের করা।
একটি বাইনারি গাছের একটি বিশেষ শর্ত রয়েছে যে প্রতিটি নোডে সর্বাধিক দুটি শিশু থাকতে পারে৷
ট্রাভার্সাল হল একটি গাছের সমস্ত নোড দেখার প্রক্রিয়া এবং তাদের মানগুলিও প্রিন্ট করতে পারে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
N = 6
আউটপুট
6
ব্যাখ্যা
Pre order traversal of tree : 1, 2, 4, 5, 3, 6, 7
সমাধান পদ্ধতি
ধারণাটি হল বাইনারি ট্রির প্রি-অর্ডার ট্রাভার্সাল ব্যবহার করা যা রিকারসিভ কল ব্যবহার করে করা হয়। প্রতিটি কলে আমরা রুট নোড পরিদর্শন করব তারপর প্রথমে বাম সাবট্রির জন্য প্রিঅর্ডার() কল করব এবং তারপরে প্রিঅর্ডার() কল করব। এই ট্রাভার্সালের সময়, আমরা নোডের সংখ্যা গণনা করব এবং নোডটি প্রিন্ট করব যার জন্য গণনা 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
