मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें जांचना है कि क्या यह ट्री एक पूर्ण बाइनरी ट्री (Complete Binary Tree) है या नहीं। लेवल n का एक पूर्ण बाइनरी ट्री में n-1 लेवल पूरी तरह भरे होते हैं, और लेवल n पर सभी नोड्स बाईं ओर से भरे होते हैं।
उदाहरण: ट्री [1,2,3,4,5,6] के लिए आउटपुट true (1) होगा, क्योंकि यह एक पूर्ण बाइनरी ट्री है।
BFS-आधारित एल्गोरिदम
- यदि ट्री खाली है, तो
trueलौटाएँ। - एक क्यू
qबनाएँ और रूट डालें। flag := trueसेट करें (यह दर्शाता है कि अब तक सभी नोड्स पूर्ण हैं)।while q खाली नहीं है:sz := q का आकार।while sz > 0:node := q से डी-क्यू किया गया नोड।- यदि
node->leftमौजूद है:- यदि
flagसेट है, तोnode->leftको एनक्यू करें, अन्यथाfalseलौटाएँ।
- यदि
- अन्यथा
flag := false। - यदि
node->rightमौजूद है:- यदि
flagसेट है, तोnode->rightको एनक्यू करें, अन्यथाfalseलौटाएँ।
- यदि
flag := false(राइट चाइल्ड के बाद कोई और चाइल्ड नहीं हो सकता)।sz--।
trueलौटाएँ।
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) { val = data; left = NULL; right = NULL; }
};
class Solution {
public:
bool isCompleteTree(TreeNode* root) {
if (!root) return true;
queue<TreeNode*> q;
q.push(root);
bool isComplete = true;
while (!q.empty()) {
int sz = q.size();
while (sz--) {
TreeNode* node = q.front(); q.pop();
if (node->left) {
if (isComplete) q.push(node->left);
else return false;
} else {
isComplete = false;
}
if (node->right) {
if (isComplete) q.push(node->right);
else return false;
} else {
isComplete = false;
}
}
}
return true;
}
};
// टेस्ट
int main() {
vector<int> v = {1,2,3,4,5,6};
// make_tree फंक्शन की आवश्यकता होगी (लेवल ऑर्डर से ट्री बनाएँ)
// यहाँ सरलता के लिए मान लें ट्री बना है
Solution ob;
// cout << ob.isCompleteTree(root);
return 0;
}
इनपुट
{1,2,3,4,5,6}
आउटपुट
1