C++-এ BST-এ দেওয়া সমষ্টির সব জোড়া বের করা

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

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

• BST নোড স্ট্রাকচার ও ইনসার্ট ফাংশন তৈরি করুন।
• দুই ভেক্টর left_side_nodes এবং right_side_nodes দিয়ে ইন-অর্ডার এবং রিভার্স ইন-অর্ডার ট্রাভার্সাল সিমুলেট করুন।
• দুই পয়েন্টার টেকনিকের মতো বাম থেকে ছোট এবং ডান থেকে বড় মান তুলনা করুন।
• যোগফল < target হলে বাম পয়েন্টার ডান দিকে, > target হলে ডান পয়েন্টার বাম দিকে, = target হলে জোড়া প্রিন্ট করুন।

উদাহরণ

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

struct Node {
    int data; Node *left, *right;
    Node(int d) : data(d), left(NULL), right(NULL) {}
};

Node* insert(Node* root, int data) {
    if (!root) return new Node(data);
    if (root->data < data) root->right = insert(root->right, data);
    else if (root->data > data) root->left = insert(root->left, data);
    return root;
}

void findPairs(Node* root, int target) {
    vector leftNodes, rightNodes;
    Node *curL = root, *curR = root;
    while (curL || curR || (!leftNodes.empty() && !rightNodes.empty())) {
        while (curL) { leftNodes.push_back(curL); curL = curL->left; }
        while (curR) { rightNodes.push_back(curR); curR = curR->right; }
        Node* ln = leftNodes.back(); Node* rn = rightNodes.back();
        int lv = ln->data, rv = rn->data;
        if (lv >= rv) break;
        if (lv + rv < target) { leftNodes.pop_back(); curL = ln->right; }
        else if (lv + rv > target) { rightNodes.pop_back(); curR = rn->left; }
        else { cout << lv << " " << rv << endl; leftNodes.pop_back(); rightNodes.pop_back(); curL = ln->right; curR = rn->left; }
    }
}

int main() {
    Node* root = NULL;
    root = insert(root, 25); root = insert(root, 20); root = insert(root, 30);
    root = insert(root, 15); root = insert(root, 21); root = insert(root, 19);
    root = insert(root, 31);
    findPairs(root, 50);
    return 0;
}

আউটপুট

19 31
20 30