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