एक बाइनरी ट्री को देखते हुए, कार्य यह जांचना है कि यह एक पूर्ण बाइनरी ट्री है या नहीं। एक बाइनरी ट्री को पूर्ण बाइनरी ट्री कहा जाता है यदि प्रत्येक नोड में शून्य या दो बच्चे हों।
उदाहरण के लिए
इनपुट-1
<मजबूत> 
आउटपुट:
1
स्पष्टीकरण: लीफ नोड को छोड़कर प्रत्येक नोड में दो बच्चे होते हैं, इसलिए यह एक पूर्ण बाइनरी ट्री है।
इनपुट-2:
<मजबूत> 
आउटपुट:
0
स्पष्टीकरण: नोड 2 में केवल एक बच्चा है, इसलिए यह पूर्ण बाइनरी ट्री नहीं है।
इस समस्या को हल करने का तरीका
यह जांचने के लिए कि दिया गया बाइनरी ट्री भरा हुआ है या नहीं, हम लेफ्ट सबट्री और राइट सबट्री के लिए रिकर्सिवली चेक कर सकते हैं।
- नोड्स और उसके बच्चों वाले बाइनरी ट्री को इनपुट करें।
- एक बूलियन फ़ंक्शन isFullBinaryTree(Node*root) इनपुट के रूप में रूट नोड लेता है और यदि यह पूर्ण बाइनरी ट्री है, तो सही है, अन्यथा गलत है।
- आधार स्थिति में, यदि रूट नोड NULL या खाली है, तो ट्रू लौटाएं।
- अगर लेफ्ट सबट्री और राइट सबट्री NULL या खाली है, तो ट्रू रिटर्न करें।
- अब हम बाएं सबट्री और राइट सबट्री के लिए पुनरावर्ती रूप से जांच करते हैं और आउटपुट वापस करते हैं।
उदाहरण
#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 के रूप में मिलता है।