C++-এ বাইনারি ট্রিতে প্রিঅর্ডার সাকসেসর (Preorder Successor of a Node)

এই সমস্যাতে, একটি বাইনারি ট্রি এবং একটি নোড ভ্যালু দেওয়া থাকে। সেই নোডের প্রিঅর্ডার সাকসেসর (প্রিঅর্ডার ট্রাভার্সালে ঠিক পরের নোড) বের করতে হবে।

উদাহরণ

ট্রি: 5 → 9, 0 → 1, 2, 5

প্রিঅর্ডার: 5, 9, 0, 1, 2, 5

ইনপুট: 9 → আউটপুট: 0

কার্যকর লজিক

• নোডের বাম চাইল্ড থাকলে → সেটিই সাকসেসর
• লিফ নোড এবং বাম চাইল্ড হলে → ভাই নোড (সিবলিং) সাকসেসর
• লিফ নোড এবং ডান চাইল্ড হলে → উপরের পূর্বজ যেটির ডান চাইল্ড আছে, তার ডান চাইল্ড সাকসেসর

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* 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* succ = preOrderSuccessorNode(root, root->left->right);
    if (succ)
        cout << "Preorder successor of " << root->left->right->key 
             << " is " << succ->key;
    else
        cout << "Preorder successor is NULL";
    return 0;
}

আউটপুট

Preorder successor of 50 is 26