এই সমস্যাতে, একটি বাইনারি ট্রি এবং একটি নোড ভ্যালু দেওয়া থাকে। সেই নোডের প্রিঅর্ডার প্রিডিসেসর (প্রিঅর্ডার ট্রাভার্সালে ঠিক আগের নোড) বের করতে হবে।
বাইনারি ট্রি ও প্রিঅর্ডার ট্রাভার্সাল
- বাইনারি ট্রি: প্রতিটি নোডের সর্বোচ্চ ২টি চাইল্ড থাকে
- প্রিঅর্ডার: রুট → বাম সাবট্রি → ডান সাবট্রি
কার্যকর লজিক
- নোড যদি রুট হয় → প্রিডিসেসর নেই (NULL)
- নোড যদি ডান চাইল্ড হয় → বাম চাইল্ডই প্রিডিসেসর
- নোড যদি বাম চাইল্ড হয় → প্যারেন্ট প্রিডিসেসর
- লিফ নোড হলে → উপরের প্যারেন্ট যেটির ডান চাইল্ড আছে সেটি প্রিডিসেসর
C++ প্রোগ্রাম উদাহরণ
#include <iostream>
using namespace std;
struct Node {
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* 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* pred = preOrderPredecessorNode(root, root->left->right);
if (pred)
cout << "Preorder Predecessor of " << root->left->right->key
<< " is " << pred->key;
else
cout << "Preorder Predecessor is NULL";
return 0;
}
আউটপুট
Preorder Predecessor of 50 is 18
