এই সমস্যায়, আমাদের একটি বাইনারি ট্রি বিটি এবং একটি মূল মান দেওয়া হয়েছে। আমাদের কাজ হল প্রদত্ত কী-এর পরবর্তী ডানদিকের নোড খুঁজে বের করা।
বাইনারি ট্রি হল একটি বিশেষ ডেটা স্ট্রাকচার যা ডেটা স্টোরেজের উদ্দেশ্যে ব্যবহৃত হয়।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
key = 4
আউটপুট
5
ব্যাখ্যা
নোড 4 এর পাশের উপাদানটি হল 5।
সমাধান পদ্ধতি
সমস্যাটির একটি সহজ সমাধান হল লেভেল অর্ডার ট্রাভার্সাল ব্যবহার করে বাইনারি ট্রি অতিক্রম করা। এবং প্রদত্ত কী মানের জন্য, আমরা পরীক্ষা করব যে ট্র্যাভারসালে একই স্তরে নোডের পাশে একটি নোড আছে কিনা। যদি হ্যাঁ, পরবর্তী নোড ফেরত দিন, অন্যথায় NULL ফেরত দিন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <iostream>
#include <queue>
using namespace std;
struct node {
struct node *left, *right;
int key;
};
node* newNode(int key) {
node *temp = new node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
node* findNextRightNodeBT(node *root, int k) {
if (root == NULL)
return 0;
queue<node *> nodeVal;
queue<int> nodeLevel;
int level = 0;
nodeVal.push(root);
nodeLevel.push(level);
while (nodeVal.size()) {
node *node = nodeVal.front();
level = nodeLevel.front();
nodeVal.pop();
nodeLevel.pop();
if (node->key == k) {
if (nodeLevel.size() == 0 || nodeLevel.front() != level)
return NULL;
return nodeVal.front();
}
if (node->left != NULL) {
nodeVal.push(node->left);
nodeLevel.push(level+1);
}
if (node->right != NULL) {
nodeVal.push(node->right);
nodeLevel.push(level+1);
}
}
return NULL;
}
int main() {
node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
int key = 4;
cout<<"The next right node of the node "<<key<<" is ";
node *nextNode = findNextRightNodeBT(root, key);
if(nextNode != NULL)
cout<<nextNode->key;
else
cout<<"not available";
return 0;
} আউটপুট
The next right node of the node 4 is 5
