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