मान लीजिए कि हमारे पास एक बाइनरी ट्री है। बाइनरी ट्री तब मान्य होता है जब वह निम्नलिखित गुणों से मिलता है।
- प्रत्येक नोड में बाएँ और दाएँ बच्चों के मानों के योग के समान डेटा मान होना चाहिए। अगर किसी भी तरफ बच्चे नहीं हैं, तो इसे 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