একটি বাইনারি সার্চ ট্রি (BST) এবং একটি টার্গেট সমষ্টি দেওয়া থাকলে, ট্রিতে যেকোনো একটি নোড জোড়া যাদের যোগফল টার্গেটের সমান সেটা বের করতে হবে।
পদ্ধতি
- BST নোড ও ইনসার্ট ফাংশন তৈরি করুন।
- দুই ভেক্টর দিয়ে ইন-অর্ডার ও রিভার্স ইন-অর্ডার ট্রাভার্সাল সিমুলেট করুন।
- দুই পয়েন্টার টেকনিকের মতো বাম থেকে ছোট, ডান থেকে বড় মান তুলনা করুন।
- যোগফল টার্গেটের সমান হলে জোড়া প্রিন্ট করে ব্রেক করুন।
উদাহরণ
#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 findPair(Node* root, int target) {
vector L, R; Node *cL=root, *cR=root;
while (cL || cR || (!L.empty() && !R.empty())) {
while (cL) { L.push_back(cL); cL = cL->left; }
while (cR) { R.push_back(cR); cR = cR->right; }
Node* ln = L.back(); Node* rn = R.back();
int lv = ln->data, rv = rn->data;
if (lv >= rv) break;
if (lv+rv < target) { L.pop_back(); cL = ln->right; }
else if (lv+rv > target) { R.pop_back(); cR = rn->left; }
else { cout << lv << " " << rv << endl; break; }
}
}
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);
findPair(root, 36);
return 0;
}
আউটপুট
15 21
