এই সমস্যায় একটি বাইনারি ট্রি এবং একটি নোড দেওয়া আছে। সেই নোডের পোস্টঅর্ডার ট্রাভার্সালে পরের নোডটি (সাক্সেসর) খুঁজে বের করতে হবে।
সংজ্ঞা
- বাইনারি ট্রি: প্রতিটি নোডের সর্বোচ্চ দুটি চাইল্ড থাকতে পারে।
- পোস্টঅর্ডার ট্রাভার্সাল: বাম সাবট্রি → ডান সাবট্রি → রুট।
উদাহরণ
ট্রির পোস্টঅর্ডার: 8 4 2 7 9 6
ইনপুট: নোড = 7
আউটপুট: 9
কার্যকর সমাধান (O(h) জটিলতা)
- রুট নোডের সাক্সেসর NULL।
- যদি নোডটি ডান চাইল্ড হয়, তবে প্যারেন্টই সাক্সেসর।
- যদি নোডটি বাম চাইল্ড হয়:
- ডান সিবলিং নেই → প্যারেন্টই সাক্সেসর।
- ডান সিবলিং আছে → সিবলিং বা তার সবচেয়ে বামে থাকা নোডটি সাক্সেসর।
C++ প্রোগ্রাম
#include <iostream>
using namespace std;
struct Node {
Node *left, *right, *parent;
int value;
};
Node* insertNode(int value) {
Node* temp = new Node;
temp->left = temp->right = temp->parent = NULL;
temp->value = value;
return temp;
}
Node* findPostorderSuccessor(Node* root, Node* n) {
if (n == root) return NULL;
Node* parent = n->parent;
if (parent->right == NULL || parent->right == n)
return parent;
Node* curr = parent->right;
while (curr->left != NULL)
curr = curr->left;
return curr;
}
int main() {
Node* root = insertNode(6);
root->parent = NULL;
root->left = insertNode(2); root->left->parent = root;
root->left->left = insertNode(8); root->left->left->parent = root->left;
root->left->right = insertNode(4); root->left->right->parent = root->left;
root->right = insertNode(9); root->right->parent = root;
root->right->left = insertNode(7); root->right->left->parent = root->right;
root->left->right->left = insertNode(14);
Node* successorNode = findPostorderSuccessor(root, root->left->right);
if (successorNode)
cout << "পোস্টঅর্ডার সাক্সেসর " << root->left->right->value << " হলো " << successorNode->value;
else
cout << "পোস্টঅর্ডার সাক্সেসর " << root->left->right->value << " হলো NULL";
return 0;
}
আউটপুট
পোস্টঅর্ডার সাক্সেসর 4 হলো 2
