এই সমস্যায়, আমরা একটি বাইনারি গাছ এবং একটি নোড মান দেওয়া হয়. আমাদের কাজ হল নোডের প্রি-অর্ডার পূর্বসূরী প্রিন্ট করা।
বাইনারি ট্রি একটি বিশেষ ধরনের গাছ যাতে প্রতিটি রুট নোডে সর্বোচ্চ 2টি চাইল্ড নোড থাকতে পারে৷
প্রাক-অর্ডার ট্রাভার্সাল গাছের নোড অতিক্রম করার একটি উপায়। এতে আমরা প্রথমে রুট নোড তারপর লেফট চাইল্ড এবং তারপর রাইট চাইল্ড অতিক্রম করব।
প্রি-অর্ডার পূর্বসূরী নোড নোড হল সেই নোড যা নোডের প্রি-অর্ডার ট্রাভার্সালে নোডের আগে আসে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক
Input: 1 Output: 9
এই সমস্যাটি সমাধান করতে, একটি নেভি পদ্ধতিটি হবে বাইনারি ট্রির প্রি-অর্ডার ট্রাভার্সাল খুঁজে বের করা এবং তারপরে প্রদত্ত সংখ্যার পরে আসা উপাদানটি প্রিন্ট করা।
একটি আরও কার্যকর সমাধানের মধ্যে প্রদত্ত সংখ্যার অবস্থান পরীক্ষা করা এবং তারপর অবস্থানের উপর ভিত্তি করে এর পূর্বসূরি অনুসন্ধান করা জড়িত। যদি নোডটি রুট নোড হয়, তাহলে NULL ফেরত দিন, কোন পূর্বসূরি নেই। যদি নোডটি ডান সন্তান হয়, তাহলে বাম শিশুটি পূর্বসূরি হবে৷
৷সমাধানের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম
উদাহরণ
#include <iostream>
using namespace std;
struct Node {
struct Node *left, *right, *parent;
int key;
};
struct Node* insertNode(int key){
Node* temp = new Node;
temp->left = temp->right = temp->parent = NULL;
temp->key = key;
return temp;
}
Node* preOrderPredecessorNode(Node* root, Node* n){
if (n == root)
return NULL;
Node* parent = n->parent;
if (parent->left == NULL || parent->left == n)
return parent;
Node* curr = parent->left;
while (curr->right != NULL)
curr = curr->right;
return curr;
}
int main() {
Node* root = insertNode(99);
root->parent = NULL;
root->left = insertNode(4);
root->left->parent = root;
root->left->left = insertNode(18);
root->left->left->parent = root->left;
root->left->right = insertNode(50);
root->left->right->parent = root->left;
root->right = insertNode(26);
root->right->parent = root;
root->right->left = insertNode(5);
root->right->left->parent = root->right;
root->right->right = insertNode(10);
root->right->right->parent = root->right;
Node* preOrderPredecessor = preOrderPredecessorNode(root, root->left->right);
if (preOrderPredecessor)
cout<<"Preorder Predecessor of "<<root->left->right->key<<" is "<<preOrderPredecessor->key;
else
cout<<"Preorder Predecessor of "<<root->left->right->key<<" is NULL";
return 0;
} আউটপুট
Preorder Predecessor of 50 is 18
