কনসেপ্ট
দেওয়া বাইনারি ট্রিতে সর্বোচ্চ কমপ্লিট সাবট্রির আকার বের করুন।
কমপ্লিট বাইনারি ট্রি − একটি বাইনারি ট্রি কমপ্লিট যদি সব লেভেল পুরনো থাকে (শেষ লেভেল বাদে) এবং শেষ লেভেলের সব কি যতটা সম্ভব বামে থাকে। সব পারফেক্ট বাইনারি ট্রি কমপ্লিট, কিন্তু বিপরীত সত্য নয়। যদি ট্রি কমপ্লিট না হয়, তবে সেটি পারফেক্টও নয়।
ইনপুট
2 / \ 3 4 / \ / \ 5 6 7 8 / \ / 9 10 11
আউটপুট
Size : 10 Inorder Traversal : 9 5 10 3 11 6 2 7 4 8 উপরের ট্রিটি একটি কমপ্লিট বাইনারি ট্রি।
ইনপুট
51 / \ 31 61 / \ / \ 6 21 46 71 / 11
আউটপুট
Size : 4(দায়া সাবট্রির জন্য) Inorder Traversal : 11 46 61 71 উপরের ট্রিটি কমপ্লিট বাইনারি ট্রি নয়।
পদ্ধতি
বটম-আপ ম্যানারে ট্রি ট্রাভার্স করুন। চাইল্ড থেকে প্যারেন্টে রিকার্শন রিটার্ন হলে সাবট্রির ইনফরমেশন পাস করুন। প্যারেন্ট সেটি ব্যবহার করে O(1) টাইমে কমপ্লিট ট্রি টেস্ট করবে। উভয় সাবট্রি বলে দেবে সেটি পারফেক্ট/কমপ্লিট কিনা এবং الآن পর্যন্ত পাওয়া গেছে সর্বোচ্চ কমপ্লিট সাবট্রির আকার।
সাবট্রি থেকে পাস করতে হবে:
- বুল ভেরিয়েবল: লेफট/রাইট সাবট্রি পারফেক্ট এবং কমপ্লিট কিনা।
- ৩টি কেস দিয়ে প্যারেন্ট কমপ্লিট কিনা চেক করুন:
- লेफট পারফেক্ট, রাইট কমপ্লিট, হাইট সমান → রুট কমপ্লিট, আকার = লেফট+রাইট+১।
- লেফট কমপ্লিট, রাইট পারফেক্ট, লেফট হাইট রাইটের চেয়ে ১ বেশি → রুট কমপ্লিট, আকার = লেফট+রাইট+১ (পারফেক্ট নয়)।
- অন্যথায় রুট কমপ্লিট নয়, লেফট/রাইটের ম্যাক্স আকার রিটার্ন করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct node1 {
int data;
struct node1* left;
struct node1* right;
};
struct node1* newNode(int data){
struct node1* node1 = (struct node1*)malloc(sizeof(struct node1));
node1->data = data;
node1->left = NULL;
node1->right = NULL;
return node1;
};
struct returnType {
bool isPerfect;
bool isComplete;
int size1;
node1* rootTree;
};
int getHeight(int size1){
return ceil(log2(size1 + 1));
}
returnType findCompleteBinaryTree(struct node1* root){
returnType rt1;
if (root == NULL) {
rt1.isPerfect = true;
rt1.isComplete = true;
rt1.size1 = 0;
rt1.rootTree = NULL;
return rt1;
}
returnType lv1 = findCompleteBinaryTree(root->left);
returnType rv1 = findCompleteBinaryTree(root->right);
if (lv1.isPerfect == true && rv1.isComplete == true && getHeight(lv1.size1) == getHeight(rv1.size1)) {
rt1.isComplete = true;
rt1.isPerfect = (rv1.isPerfect ? true : false);
rt1.size1 = lv1.size1 + rv1.size1 + 1;
rt1.rootTree = root;
return rt1;
}
if (lv1.isComplete == true && rv1.isPerfect == true && getHeight(lv1.size1) == getHeight(rv1.size1) + 1) {
rt1.isComplete = true;
rt1.isPerfect = false;
rt1.size1 = lv1.size1 + rv1.size1 + 1;
rt1.rootTree = root;
return rt1;
}
rt1.isPerfect = false;
rt1.isComplete = false;
rt1.size1 = max(lv1.size1, rv1.size1);
rt1.rootTree = (lv1.size1 > rv1.size1 ? lv1.rootTree : rv1.rootTree);
return rt1;
}
void inorderPrint(node1* root){
if (root != NULL) {
inorderPrint(root->left);
cout << root->data << " ";
inorderPrint(root->right);
}
}
int main(){
struct node1* root = newNode(50);
root->left = newNode(30);
root->right = newNode(60);
root->left->left = newNode(5);
root->left->right = newNode(20);
root->right->left = newNode(45);
root->right->right = newNode(70);
root->right->left->left = newNode(10);
struct returnType ans1 = findCompleteBinaryTree(root);
cout << "Size : " << ans1.size1 << endl;
cout << "Inorder Traversal : ";
inorderPrint(ans1.rootTree);
return 0;
} আউটপুট
Size : 4 Inorder Traversal : 10 45 60 70
