এই সমস্যায়, আমাদের একটি বাইনারি ট্রি দেওয়া হয়। এবং আমাদের খুঁজে বের করতে হবে মূল থেকে পাতার পথে একটি জোড়া আছে কিনা যার যোগফল রুটের ডেটার সমান।
রুট নোড থেকে লিফ নোডের মধ্যে একটি জোড়া নোড আছে কিনা তা আমাদের পরীক্ষা করতে হবে যাতে জোড়ার মানগুলির যোগফল রুট নোডের মানের সমান হয়৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট:
আউটপুট: হ্যাঁ
ব্যাখ্যা:
রুট নোড মান 7
রুট নোড, (2, 5), (1, 6) এর সমান সমমূল্য সহ জোড়া।
সমাধান পদ্ধতি:
আমাদের গাছটি অতিক্রম করতে হবে এবং হ্যাশিং ব্যবহার করে জোড়া খুঁজে বের করতে হবে।
এর জন্য আমরা একটি হ্যাশটেবল এবং ট্রাভার্স ট্রি তৈরি করব। হ্যাশটেবলে ডেটা সন্নিবেশ করুন এবং তারপরে অন্যান্য উপাদানগুলির সাথে এর যোগফল রুটের সমান কিনা তা পরীক্ষা করুন৷
এবং শেষে, যদি আমরা কোন জোড়া না পাই, তাহলে false ফেরত দিন।
জোড়া পাওয়া গেলে, সত্য ফেরত দিন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* left, *right;
};
struct Node* newnode(int data) {
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
bool findSumUntill(Node *node, unordered_set<int> &hashTable, int rootVal)
{
if (node == NULL)
return false;
int otherVal = rootVal - node->data;
if (hashTable.find(otherVal) != hashTable.end())
return true;
hashTable.insert(node->data);
bool isFound = findSumUntill(node->left, hashTable, rootVal) || findSumUntill(node->right, hashTable, rootVal);
hashTable.erase(node->data);
return isFound;
}
bool findPairSum(Node *root) {
unordered_set<int> hashTable;
return findSumUntill(root->left, hashTable, root->data) || findSumUntill(root->right, hashTable, root->data);
}
int main()
{
struct Node *root = newnode(7);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(5);
root->left->right = newnode(9);
root->left->left->left = newnode(1);
root->left->left->right = newnode(6);
root->right->left = newnode(8);
if(findPairSum(root))
cout<<"Pair with sum equal to root value found";
else
cout<<"No pairs found";
return 0;
} আউটপুট
Pair with sum equal to root value found
