আমাদের একটি ইন্টিজার ভ্যালু এবং একটি ভেরিয়েবল x দেওয়া আছে। টাস্ক হলো বাইনারি ট্রি নির্মাণ করা এবং সেই জোড়াগুলো খুঁজে বের করা যাদের যোগফল x-এর সমান।
ইনপুট
x = 5, ইনপুট ভ্যালুগুলো থেকে যে ট্রি তৈরি হবে वो নিচে দেওয়া আছে:
আউটপুট
Count of pairs in a binary tree whose sum is equal to a given value x are: 2
ব্যাখ্যা
আমাদের একটি ইন্টিজার অ্যারে দেওয়া আছে जिससे বাইনারি ট্রি তৈরি করা হয়েছে। আমরা চেক করব কোনো জোড়া আছে কিনা যাদের যোগফল x (৫) এর সমান। জোড়াগুলো হলো (2, 3) এবং (1, 4)।
ইনপুট
x = 8, ইনপুট ভ্যালুগুলো থেকে যে ট্রি তৈরি হবে वो নিচে দেওয়া আছে:
আউটপুট
Count of pairs in a binary tree whose sum is equal to a given value x are: 3
ব্যাখ্যা
আমাদের একটি ইন্টিজার অ্যারে দেওয়া আছে जिससे বাইনারি ট্রি তৈরি করা হয়েছে। আমরা চেক করব কোনো জোড়া আছে কিনা যাদের যোগফল x (৮) এর সমান। জোড়াগুলো হলো (2, 6), (4, 4) এবং (5, 3)।
প্রোগ্রামে ব্যবহৃত পদ্ধতি:
- একটি নোড স্ট্রাকচার তৈরি করা হয় যাতে থাকে ডেটা পার্ট এবং লেফট, রাইট পয়েন্টার।
- ইন্টিজার ভ্যালু ইনপুট নিয়ে লেফট ও রাইট পয়েন্টারের মাধ্যমে বাইনারি ট্রি তৈরি করা হয়।
- x ভ্যালু ইনপুট নেওয়া হয় যা জোড়ার যোগফল হিসেবে ব্যবহার হবে।
- একটি বুলিয়ান ফাংশন তৈরি করা হয় যা চেক করে জোড়ার যোগফল x কিনা।
- ফাংশনের ভিতরে: রুট NULL হলে false রিটার্ন।
- রুট != ptr এবং রুটের ডেটা + ptr-এর ডেটা == x হলে true রিটার্ন।
- রিকারসিভলি চেক ফাংশন কল করা হয় লেফট এবং রাইট পয়েন্টারের জন্য।
total_pairsফাংশন জোড়ার কাউন্ট গণনা করে।- ptr NULL হলে 0 রিটার্ন।
- চেক ফাংশন true রিটার্ন করলে টোটাল পেয়ার বাড়ানো হয়।
- রিকারসিভলি লেফট ও রাইট সাবট্রির জন্য কল করা হয়।
- ফলাফল টোটাল ভেরিয়েবলে স্টোর করে প্রিন্ট করা হয়।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct tree_node {
int data;
tree_node *left, *right;
};
tree_node* create_node(int data) {
tree_node* newNode = (tree_node*)malloc(sizeof(tree_node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
bool check(tree_node* root, tree_node* ptr, int x) {
if (root == NULL) {
return false;
}
if (root != ptr && ((root->data + ptr->data) == x)) {
return true;
}
if (check(root->left, ptr, x) || check(root->right, ptr, x)) {
return true;
}
return false;
}
void total_pairs(tree_node* root, tree_node* ptr, int x, int& total) {
if (ptr == NULL) {
return;
}
if (check(root, ptr, x) == true) {
total++;
}
total_pairs(root, ptr->left, x, total);
total_pairs(root, ptr->right, x, total);
}
int main() {
int x = 5;
int total = 0;
tree_node* root = create_node(5);
root->left = create_node(2);
root->right = create_node(3);
root->left->left = create_node(1);
root->left->right = create_node(4);
root->right->left = create_node(6);
total_pairs(root, root, x, total);
total = total / 2;
cout << "Count of pairs in a binary tree whose sum is equal to a given value x are: " << total;
return 0;
}
আউটপুট
Count of pairs in a binary tree whose sum is equal to a given value x are: 2
