एक बाइनरी ट्री दिया गया है, कार्य यह जांचना है कि यह फुल बाइनरी ट्री है या नहीं। एक बाइनरी ट्री को फुल बाइनरी ट्री कहा जाता है यदि प्रत्येक नोड के शून्य या दो बच्चे हैं।
उदाहरण के लिए
इनपुट-1
आउटपुट:
1
व्याख्या: लीफ नोड को छोड़कर हर नोड के दो बच्चे हैं, इसलिए यह एक फुल बाइनरी ट्री है।
इनपुट-2:
आउटपुट:
0
व्याख्या: नोड 2 का केवल एक बच्चा है, इसलिए यह फुल बाइनरी ट्री नहीं है।
इस समस्या को हल करने का दृष्टिकोण
यह जांचने के लिए कि दिया गया बाइनरी ट्री फुल है या नहीं, हम बाएं सबट्री और दाएं सबट्री के लिए पुनरावर्ती रूप से जांच सकते हैं।
- नोड्स और उसके बच्चों वाले दिए गए बाइनरी ट्री को इनपुट करें।
- एक बूलियन फ़ंक्शन isFullBinaryTree(Node*root) रूट नोड को इनपुट के रूप में लेता है और यदि यह फुल बाइनरी ट्री है तो True लौटाता है, अन्यथा false।
- बेस कंडीशन में, यदि रूट नोड NULL या खाली है, तो True लौटाएं।
- यदि बायां सबट्री और दायां सबट्री NULL या खाली है, तो True लौटाएं।
- अब आइए बाएं सबट्री और दाएं सबट्री में से प्रत्येक के लिए पुनरावर्ती रूप से जांचें और आउटपुट लौटाएं।
उदाहरण
#include<iostream>
using namespace std;
struct treenode {
int data;
treenode * left;
treenode * right;
};
struct treenode * createNode(int d) {
struct treenode * root = new treenode;
root -> data = d;
root -> left = NULL;
root -> right = NULL;
return root;
}
bool isFullBinaryTree(struct treenode * root) {
if (root == NULL) {
return true;
}
if (root -> left == NULL and root -> right == NULL) {
return true;
} else if (root -> left and root -> right) {
return (isFullBinaryTree(root -> left) and isFullBinaryTree(root -> right));
}
return false;
}
int main() {
struct treenode * root = NULL;
root = createNode(1);
root -> left = createNode(2);
root -> right = createNode(3);
root -> left -> right = createNode(4);
root -> left -> left = createNode(5);
root -> right -> left = createNode(6);
if (isFullBinaryTree(root)) {
cout << "1" << endl;
} else {
cout << "0" << endl;
}
return 0;
}
उपरोक्त कोड चलाने से आउटपुट इस प्रकार उत्पन्न होगा,
आउटपुट
0
व्याख्या: चूंकि दिए गए बाइनरी ट्री में सभी लीफ नोड्स के बच्चे नोड्स नहीं हैं, यह फुल बाइनरी ट्री नहीं है। इसलिए, हमें आउटपुट 0 मिलता है।
