এখানে আমরা দেখব কিভাবে একটি বাইনারি ট্রি সম-ট্রি (SumTree) কিনা তা নির্ধারণ করা যায়। সম-ট্রি হলো এমন একটি বাইনারি ট্রি যেখানে প্রতিটি নোড তার বাম ও ডান সন্তানের মানগুলোর যোগফল ধারণ করে। ট্রির রুট নোডটি পুরো ট্রির সব নোডের মানের যোগফল ধারণ করে। নিচে একটি সম-ট্রির উদাহরণ দেওয়া হলো:
এটি যাচাই করতে আমরা একটি সাধারণ ট্রিক ব্যবহার করব: বাম ও ডান সাবট্রির সব নোডের মানগুলোর যোগফল বের করব। যদি সেই যোগফলটি রুট নোডের মানের সমান হয়, তবে সেটি সম-ট্রি। এটি একটি রিকার্সিভ পদ্ধতিতে করা যায়।
উদাহরণ
#include <bits/stdc++.h> using namespace std; class node { public: int data; node* left, *right; }; int sum_of_nodes(node *root) { if(root == NULL) return 0; return sum_of_nodes(root->left) + root->data + sum_of_nodes(root->right); } int isSumTree(node* node) { int left_sum, right_sum; if(node == NULL || (node->left == NULL && node->right == NULL)) return 1; left_sum = sum_of_nodes(node->left); right_sum = sum_of_nodes(node->right); if((node->data == left_sum + right_sum) && isSumTree(node->left) && isSumTree(node->right)) return 1; return 0; } node* getNode(int data) { node* newNode = new node(); newNode->data = data; newNode->left = newNode->right = NULL; return newNode; } int main() { node *root = getNode(26); root->left = getNode(10); root->right = getNode(3); root->left->left = getNode(4); root->left->right = getNode(6); root->right->right = getNode(3); if(isSumTree(root)) cout << "The tree is Sum Tree"; else cout << "The tree is not a Sum Tree"; }আউটপুট
The tree is Sum Tree
