একটি বাইনারি ট্রি এবং একটি মান x ইনপুট হিসেবে দেওয়া আছে। লক্ষ্য হলো বাইনারি ট্রির সেই সাবট্রিগুলো খুঁজে বের করা যাদের নোডগুলোর ওজনের যোগফল x-এর সমান।
ইনপুট
x = 14। ইনপুট ভ্যালুগুলো থেকে যে ট্রি তৈরি হবে वो নিচে দেওয়া আছে:
আউটপুট
Count of subtrees that sum up to a given value x are: 1
ব্যাখ্যা
আমাদের x ভ্যালু ১৪ দেওয়া আছে। দেখা যাচ্ছে শুধু একটি লিফ নোড আছে যার মান ১৪, তাই কাউন্ট ১।
ইনপুট
x = 33। ইনপুট ভ্যালুগুলো থেকে যে ট্রি তৈরি হবে वो নিচে দেওয়া আছে:
আউটপুট
Count of subtrees that sum up to a given value x are: 2
ব্যাখ্যা
আমাদের x ভ্যালু ৩৩ দেওয়া আছে। দেখা যাচ্ছে দুটি সাবট্রি আছে যাদের যোগফল ৩৩, তাই কাউন্ট ২।
প্রোগ্রামে ব্যবহৃত পদ্ধতি:
এই পদ্ধতিতে আমরা রিকারসিভলি রুট নোডের লেফট সাবট্রি এবং রাইট সাবট্রির ওজনের যোগফল গণনা করি এবং শেষে রুটের ওজন যোগ করি। যদি সম x-এর সমান হয় তবে কাউন্ট বাড়ানো হয়।
- একটি ট্রি
Tree_Nodeতৈরি করা হয় রুট পয়েন্টার সহ। insert_Node(int data)ফাংশন ট্রিতে নোড যোগ করে।subtrees_x(Tree_Node* root, int x)ফাংশন রুট পয়েন্টার এবং x নিয়ে যোগফল x হয় এমন সাবট্রির কাউন্ট রিটার্ন করে।- স্ট্যাটিক ভেরিয়েবল
count০ এবংTree_Node* temp = root। Left_subtree = 0, Right_subtree = 0লেফট ও রাইট সাবট্রির নোড ওজনের যোগফলের জন্য।- রুট NULL হলে সাম ০ রিটার্ন।
Left_subtree += subtrees_x(root->Left, x)লেফট সাবট্রির নোডের যোগফল।Right_subtree += subtrees_x(root->Right, x)রাইট সাবট্রির নোডের যোগফল।sum = Left_subtree + Right_subtree + root->data।sum == xহলেcount++।temp != rootহলে (স্টার্ট নোড নয়)Left_subtree + root->data + Right_subtreeরিটার্ন।- শেষে
countরিটার্ন করা হয় যেটি x সমান যোগফল বিশিষ্ট ট্রির কাঙ্ক্ষিত সংখ্যা।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Tree_Node {
int data;
Tree_Node *Left, *Right;
};
Tree_Node* insert_Node(int data) {
Tree_Node* new_node = (Tree_Node*)malloc(sizeof(Tree_Node));
new_node->data = data;
new_node->Left = new_node->Right = NULL;
return new_node;
}
int subtrees_x(Tree_Node* root, int x) {
static int count = 0;
static Tree_Node* temp = root;
int Left_subtree = 0, Right_subtree = 0;
if (root == NULL) {
return 0;
}
Left_subtree += subtrees_x(root->Left, x);
Right_subtree += subtrees_x(root->Right, x);
int sum = Left_subtree + Right_subtree + root->data;
if (sum == x) {
count++;
}
if (temp != root) {
int set = Left_subtree + root->data + Right_subtree;
return set;
}
return count;
}
int main() {
Tree_Node* root = insert_Node(10);
root->Left = insert_Node(20);
root->Right = insert_Node(12);
root->Left->Left = insert_Node(14);
root->Left->Right = insert_Node(1);
root->Right->Left = insert_Node(21);
root->Right->Right = insert_Node(11);
int x = 14;
cout << "Count of subtrees that sum up to a given value x are: " << subtrees_x(root, x);
return 0;
}
আউটপুট
Count of subtrees that sum up to a given value x are: 1
