আমাদের একটি পূর্ণসংখ্যার মান এবং একটি পরিবর্তনশীল x দেওয়া হয়েছে এবং কাজটি হল বাইনারি ট্রি তৈরি করা এবং প্রদত্ত মানের x এর সমতুল্য যোগফলযুক্ত জোড়াগুলি খুঁজে বের করা৷
উদাহরণস্বরূপ
ইনপুট
int x =5, মান ইনপুট করার পরে যে গাছটি তৈরি হবে তা নীচে দেওয়া হল -
আউটপুট
Count of pairs in a binary tree whose sum is equal to a given value x are: 2
ব্যাখ্যা
we are given with an array of integer values that is used to form a binary tree and we will check whether there is a pair present in a binary tree whose sum equals to the given value x which is 5. So, the pairs formed are (2, 3) and (1, 4).
ইনপুট
int x =8, মান ইনপুট করার পরে যে গাছটি তৈরি হবে তা নীচে দেওয়া হল −
আউটপুট
Count of pairs in a binary tree whose sum is equal to a given value x are: 3
ব্যাখ্যা
we are given with an array of integer values that is used to form a binary tree and we will check whether there is a pair present in a binary tree whose sum equals to the given value x which is 8. So, the pairs formed are (2, 6), (4, 4) and (5, 3).
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি −
-
একটি নোডের একটি কাঠামো তৈরি করুন যাতে ডেটা অংশ এবং বাম এবং ডান পয়েন্টার থাকে যা বাম এবং ডান সাবট্রিতে নির্দেশিত হবে।
-
একটি পূর্ণসংখ্যা মান ইনপুট করুন এবং বাম এবং ডান পয়েন্টারের মাধ্যমে নোডে ডেটা প্রবেশ করে একটি বাইনারি ট্রি তৈরি করতে ব্যবহার করুন৷
-
x এর একটি মান ইনপুট করুন যা x হিসাবে যোগফলের মান সহ জোড়া গণনা করতে ব্যবহৃত হবে।
-
জোড়ার যোগফল x কি না তা পরীক্ষা করার জন্য একটি বুলিয়ান ফাংশন তৈরি করুন।
-
ফাংশনের ভিতরে, রুটটি NULL কিনা তা পরীক্ষা করুন তারপর False দিন
-
চেক করুন যদি রুট ptr এর সমান না হয় এবং root এর ডাটা + ptr এর ডাটা x এর সমান হয় তারপর ট্রু রিটার্ন করুন।
-
রুট, ptr এবং মান x এর বাম পয়েন্টার এবং x, ptr এবং x এর ডান পয়েন্টার পাস করে পুনরাবৃত্তভাবে চেক ফাংশনটি কল করুন। এখন পরীক্ষা করুন যে কোনো শর্ত সত্য হচ্ছে কিনা তারপর সত্য ফিরে আসুন।
-
অন্যথায়, মিথ্যা ফেরত দিন।
-
যোগফল x
সহ জোড়ার সংখ্যা গণনা করতে একটি ফাংশন total_pairs তৈরি করুন -
ফাংশনের ভিতরে, ptr NULL কিনা তা পরীক্ষা করুন তারপর 0 দিন।
-
একটি আর্গুমেন্ট হিসাবে root, ptr এবং x পাস করে ফাংশন চেক কল করুন। যদি ফাংশনটি সত্য হয় তাহলে মোট জোড়ার মান 1 দ্বারা বৃদ্ধি করুন
-
কল ফাংশন total_pairs recursively root, ptr এর বাম পয়েন্টার, x এবং total এবং পাস রুট, ptr এর ডান পয়েন্টার, x এবং total।
-
একটি পরিবর্তনশীল মোট সংরক্ষিত একটি পূর্ণসংখ্যা মান হিসাবে ফলাফল প্রিন্ট করুন।
উদাহরণ
#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;
}
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
