C++-এ দুটি BST-র নোড জোড়া যাদের যোগফল x গণনা

আমাদের দুটি বাইনারি সার্চ ট্রি (BST) এবং একটি মান x দেওয়া আছে। লক্ষ্য হল দুটি BST-র নোড থেকে এমন জোড়া বের করা যাদের ডেটা যোগফল x।

উদাহরণ

ইনপুট: BST-র চিত্র দেওয়া আছে।

আউটপুট: ১

ব্যাখ্যা: জোড়া: (8,6)।

অ্যালগরিদম (ইটারেটিভ ইনঅর্ডার ট্রাভার্সাল)

1. BST-১ কে ইনঅর্ডার (ছোট থেকে বড়) এবং BST-২ কে রিভার্স ইনঅর্ডার (বড় থেকে ছোট) ট্রাভার্স করুন।
2. দুটি স্ট্যাক ব্যবহার করুন।
3. BST-১-র সবচেয়ে ছোট নোড এবং BST-২-র সবচেয়ে বড় নোড থেকে শুরু করুন।
4. যোগফল temp হিসাব করুন:
   • temp == x: কাউন্ট বাড়ান, দুটি স্ট্যাক থেকে পপ করুন, BST-১-র সাকসেসর এবং BST-২-র প্রিডিসেসর-এ যান।
   • temp < x: BST-১-র স্ট্যাক থেকে পপ করুন, সাকসেসর-এ যান।
   • temp > x: BST-২-র স্ট্যাক থেকে পপ করুন, প্রিডিসেসর-এ যান।
5. কোনো স্ট্যাক খালি হলে ব্রেক করুন।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

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

Tree* insert_node(int data) {
    Tree* newNode = new Tree();
    newNode->data = data;
    newNode->left = newNode->right = nullptr;
    return newNode;
}

int BST_sum_x(Tree* BST_1, Tree* BST_2, int x) {
    int count = 0;
    stack stack_1, stack_2;
    
    if (!BST_1 || !BST_2) return 0;
    
    while (true) {
        while (BST_1) {
            stack_1.push(BST_1);
            BST_1 = BST_1->left;
        }
        while (BST_2) {
            stack_2.push(BST_2);
            BST_2 = BST_2->right;
        }
        if (stack_1.empty() || stack_2.empty()) break;
        
        Tree* top1 = stack_1.top();
        Tree* top2 = stack_2.top();
        int temp = top1->data + top2->data;
        
        if (temp == x) {
            count++;
            stack_1.pop(); stack_2.pop();
            BST_1 = top1->right;
            BST_2 = top2->left;
        } else if (temp < x) {
            stack_1.pop();
            BST_1 = top1->right;
        } else {
            stack_2.pop();
            BST_2 = top2->left;
        }
    }
    return count;
}

int main() {
    // BST 1
    Tree* BST_1 = insert_node(15);
    BST_1->left = insert_node(10);
    BST_1->right = insert_node(8);
    BST_1->left->left = insert_node(12);
    BST_1->left->right = insert_node(24);
    BST_1->right->left = insert_node(16);
    
    // BST 2
    Tree* BST_2 = insert_node(20);
    BST_2->left = insert_node(16);
    BST_2->right = insert_node(4);
    BST_2->left->left = insert_node(18);
    BST_2->left->right = insert_node(28);
    BST_2->right->left = insert_node(22);
    
    int x = 28;
    cout << "Count of pairs from two BSTs whose sum is equal to a given value x are: " 
         << BST_sum_x(BST_1, BST_2, x);
    return 0;
}

আউটপুট

Count of pairs from two BSTs whose sum is equal to a given value x are: 1