ধরুন আমাদের একটি বাইনারি গাছ আছে। বাইনারি ট্রি বৈধ হয় যখন এটি নিম্নলিখিত বৈশিষ্ট্য পূরণ করে।
- প্রতিটি নোডে ডাটা মান থাকা উচিত বাম এবং ডান চিলড্রেন মানের সমষ্টির সমান। যদি কোন পাশে কোন শিশু না থাকে, তাহলে এটিকে 0 হিসাবে গণ্য করা হবে।
ধরুন নিচের মত একটি গাছ আছে, যা প্রদত্ত সম্পত্তির সাথে মিলিত হয়।
এটি পরীক্ষা করার মতো কোন কৌশল নেই, আমাদেরকে বারবার গাছটি অতিক্রম করতে হবে, যদি নোড এবং এর উভয় সন্তান সম্পত্তিটি সন্তুষ্ট করে তবে সত্য ফেরত দেয়, অন্যথায় মিথ্যা।
উদাহরণ
#include <iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
};
bool isValidBinaryTree(node* nd) {
int left_data = 0, right_data = 0;
if(nd == NULL || (nd->left == NULL && nd->right == NULL))
return 1;
else{
if(nd->left != NULL)
left_data = nd->left->data;
if(nd->right != NULL)
right_data = nd->right->data;
if((nd->data == left_data + right_data)&& isValidBinaryTree(nd->left) && isValidBinaryTree(nd->right))
return true;
else
return false;
}
}
node* getNode(int data) {
node* newNode = new node();
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int main() {
node *root = getNode(10);
root->left = getNode(8);
root->right = getNode(2);
root->left->left = getNode(3);
root->left->right = getNode(5);
root->right->right = getNode(2);
if(isValidBinaryTree(root))
cout << "The tree satisfies the children sum property ";
else
cout << "The tree does not satisfy the children sum property ";
} আউটপুট
The tree satisfies the children sum property
