পোস্ট-অর্ডার ট্রাভার্সেলে n-তম নোড খুঁজে বের করা C++-এ

এই সমস্যায়, আমাদের একটি বাইনারি ট্রি এবং একটি পূর্ণসংখ্যা N দেওয়া আছে। কাজ হল বাইনারি ট্রির পোস্ট-অর্ডার ট্রাভার্সেলে n-তম নোড খুঁজে বের করা।

বাইনারি ট্রিতে প্রতিটি নোডের সর্বোচ্চ দুটি চাইল্ড হতে পারে।

ট্রাভার্সেল হল একটি প্রসেস যা ট্রির সব নোড ভিজিট করে এবং তাদের মান প্রিন্ট করতে পারে।

উদাহরণ

ইনপুট

N = 6

আউটপুট

3

ব্যাখ্যা

ট্রির পোস্ট-অর্ডার ট্রাভার্সেল: 4, 5, 2, 6, 7, 3, 1

সমাধানের পদ্ধতি

আইডিয়া হল বাইনারি ট্রির পোস্ট-অর্ডার ট্রাভার্সেল ব্যবহার করা যা রিকারসিভ কল দিয়ে করা হয়। প্রতিটি কলেই আমরা বাম সাবট্রির জন্য postOrder() কল করব, তারপর ডান সাবট্রির জন্য postOrder() কল করব, এবং শেষে রুট নোড ভিজিট করব। এই ট্রাভার্সেলের সময় নোড কাউন্ট করব এবং যেটির কাউন্ট N, সেই নোড প্রিন্ট করব।

প্রোগ্রাম উদাহরণ (সমস্যায় কোড মিসম্যাচ রয়েছে)

#include <iostream>
using namespace std;

bool isAPrimeNumber(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n%2 == 0 || n%3 == 0) return false;
    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
            return false;
    return true;
}

long int calcPrimeProduct(long int n) {
    long int p = 2;
    n--;
    for (int i = 3; n != 0; i++) {
        if (isAPrimeNumber(i)) {
            p = p * i;
            n--;
        }
        i++;
    }
    return p;
}

long int findNextPrime(long int n) {
    long int nextPrime = n + 2;
    while (true) {
        if (isAPrimeNumber(nextPrime))
            break;
        nextPrime++;
    }
    return nextPrime;
}

int main() {
    long long int N = 5;
    long long int primeProduct = calcPrimeProduct(N);
    int fortunateNumber = findNextPrime(primeProduct) - primeProduct;
    cout << N << "th fortunate number is " << fortunateNumber;
    return 0;
}

আউটপুট

5th fortunate number is 23

দ্রষ্টব্য: প্রদত্ত কোডটি পোস্ট-অর্ডার ট্রাভার্সেলের সমস্যা সমাধান করছে না, বরং ফর্চুনেট নম্বর বের করছে। পোস্ট-অর্ডার ট্রাভার্সেলে Nতম নোড বের করার সঠিক প্রোগ্রাম নিচে দেওয়া হলো:

সঠিক প্রোগ্রাম উদাহরণ

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
};

struct Node* createNode(int item) {
    Node* temp = new Node;
    temp->data = item;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

void findPostOrderTraversalRec(struct Node* root, int N) {
    static int nodeCount = 0;
    if (root == NULL)
        return;
    
    if (nodeCount <= N) {
        findPostOrderTraversalRec(root->left, N);
        findPostOrderTraversalRec(root->right, N);
        nodeCount++;
        if (nodeCount == N)
            cout << root->data;
    }
}

int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    
    int N = 6;
    cout << N << "th node in postorder traversal is ";
    findPostOrderTraversalRec(root, N);
    return 0;
}

আউটপুট

6th node in postorder traversal is 3