ধরুন আমাদের একটি বাইনারি ট্রি আছে। বাইনারি ট্রিটি তখনই বৈধ হবে যখন নিচের প্রোপার্টি মেনে চলে:
- প্রতিটি নোডে ডেটা ভ্যালু তার বাম ও ডান চাইল্ডের ভ্যালুগুলোর যোগফলের সমান থাকবে। যদি কোনো পাশে চাইল্ড না থাকে, তবে সেটিকে ০ ধরা হবে।
নিচে একটি ট্রি দেওয়া হলো যা প্রোপার্টিটি মেনে চলে:
এটি যাচাই করার কোনো ট্রিক নেই, আমরা ট্রি রিকার্সিভলি ট্রাভার্স করব। যদি নোড এবং তার দুটি চাইল্ড প্রোপার্টিটি সন্তুষ্ট করে, তবে true রিটার্ন করব, অন্যথায় false।
উদাহরণ
#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
