এই সমস্যায়, আমাদের একটি বাইনারি ট্রি এবং একটি পূর্ণসংখ্যা N দেওয়া আছে। কাজ হল বাইনারি ট্রির ইনঅর্ডার ট্রাভার্সেলে n-তম নোড খুঁজে বের করা।
বাইনারি ট্রিতে প্রতিটি নোডের সর্বোচ্চ দুটি চাইল্ড হতে পারে।
ট্রাভার্সেল হল একটি প্রসেস যা ট্রির সব নোড ভিজিট করে এবং তাদের মান প্রিন্ট করতে পারে।
উদাহরণ
ইনপুট
N = 6
আউটপুট
3
ব্যাখ্যা
ট্রির ইনঅর্ডার ট্রাভার্সেল: 4, 2, 5, 1, 6, 3, 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 findInOrderTraversalRec(struct Node* node, int N) {
static int count = 0;
if (node == NULL)
return;
if (count <= N) {
findInOrderTraversalRec(node->left, N);
count++;
if (count == N)
cout << node->data;
findInOrderTraversalRec(node->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 inorder traversal is ";
findInOrderTraversalRec(root, N);
return 0;
}
আউটপুট
6th node in inorder traversal is 3
