এই সমস্যায়, আমাদের একটি বাইনারি ট্রি BT এবং একটি কী ভ্যালু দেওয়া আছে। আমাদের কাজ হল দেওয়া কীর নেক্সট রাইট নোড খুঁজে বের করা।
বাইনারি ট্রি হল একটি বিশেষ ডেটা স্ট্রাকচার যা ডেটা স্টোরেজের জন্য ব্যবহৃত হয়।
উদাহরণ
ইনপুট
key = 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 NULL;
queue<node*> nodeVal;
queue<int> nodeLevel;
int level = 0;
nodeVal.push(root);
nodeLevel.push(level);
while (!nodeVal.empty()) {
node *currNode = nodeVal.front();
level = nodeLevel.front();
nodeVal.pop();
nodeLevel.pop();
if (currNode->key == k) {
if (nodeLevel.empty() || nodeLevel.front() != level)
return NULL;
return nodeVal.front();
}
if (currNode->left != NULL) {
nodeVal.push(currNode->left);
nodeLevel.push(level + 1);
}
if (currNode->right != NULL) {
nodeVal.push(currNode->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
