এই টিউটোরিয়ালে, আমরা একটি প্রোগ্রাম লিখতে যাচ্ছি যেটি একটি বাইনারি গাছের তির্যক ট্রাভার্সালে k-th নোড খুঁজে পায়।
আসুন সমস্যা সমাধানের পদক্ষেপগুলি দেখি৷
৷- কিছু নমুনা ডেটা দিয়ে বাইনারি ট্রি শুরু করুন।
- k সংখ্যাটি শুরু করুন।
- ডাটা স্ট্রাকচার কিউ ব্যবহার করে তির্যকভাবে বাইনারি ট্রি অতিক্রম করুন।
- প্রতিটি নোডে k-এর মান হ্রাস করুন।
- k 0 হয়ে গেলে নোডটি ফেরত দিন।
- রিটার্ন -1 যদি এরকম কোন নোড না থাকে।
উদাহরণ
আসুন কোডটি দেখি।
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
Node* getNewNode(int data) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
int findDiagonalKthElement(Node* root, int k) {
if (root == NULL || k == 0) {
return -1;
}
int result = -1;
queue<Node*> q;
q.push(root);
q.push(NULL);
while (!q.empty()) {
Node* temp = q.front();
q.pop();
if (temp == NULL) {
if (q.empty()) {
if (k == 0) {
return result;
}else {
break;
}
}
q.push(NULL);
}else {
while (temp) {
if (k == 0) {
return result;
}
k--;
result = temp->data;
if (temp->left) {
q.push(temp->left);
}
temp = temp->right;
}
}
}
return -1;
}
int main() {
Node* root = getNewNode(10);
root->left = getNewNode(5);
root->right = getNewNode(56);
root->left->left = getNewNode(3);
root->left->right = getNewNode(22);
root->right->right = getNewNode(34);
root->right->right->left = getNewNode(45);
root->left->right->left = getNewNode(67);
root->left->right->right = getNewNode(100);
int k = 9;
cout << findDiagonalKthElement(root, k) << endl;
return 0;
} আউটপুট
আপনি যদি উপরের কোডটি চালান, তাহলে আপনি নিম্নলিখিত ফলাফল পাবেন।
67
উপসংহার
টিউটোরিয়ালে আপনার কোন প্রশ্ন থাকলে মন্তব্য বিভাগে উল্লেখ করুন।
