এই সমস্যায়, আমাদের একটি বাইনারি ট্রি দেওয়া আছে। এবং আমাদের রুট থেকে লিফ পাথে এমন একটি জোড়া খুঁজে বের করতে হবে যাদের যোগফল রুট নোডের ডেটার সমান।
আমাদের যাচাই করতে হবে যে রুট নোড থেকে লিফ নোড পর্যন্ত এমন কোনো নোড জোড়া আছে কিনা যাদের মান যোগ করলে রুট নোডের মানের সমান হয়।
উদাহরণ দিয়ে বুঝি,
ইনপুট:
আউটপুট: হ্যাঁ
ব্যাখ্যা:
রুট নোডের মান ৭
রুটের মানের সমান যোগফলযুক্ত জোড়া: (২, ৫), (১, ৬)।
সমাধানের পদ্ধতি:
আমাদের ট্রি ট্রাভার্সাল করে হ্যাশিং দিয়ে জোড়া খুঁজে বের করতে হবে।
এজন্য আমরা একটি হ্যাশ টেবিল তৈরি করব এবং ট্রি ট্রাভার্স করব। ডেটা হ্যাশ টেবিলে डालব এবং দেখব অন্য কোনো এলিমেন্টের সাথে যোগ করলে রুটের মান হয় কিনা।
- যদি কোনো জোড়া না পাওয়া যায়, false রিটার্ন করুন।
- যদি জোড়া পাওয়া যায়, true রিটার্ন করুন।
সমাধান দর্শানোর প্রোগ্রাম,
উদাহরণ
#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
