বাইনারি ট্রির পূর্ণতা যাচাই C++-এ

ধরা যাক একটি বাইনারি ট্রি আছে। আমরা যাচাই করব যে ট্রিটি পূর্ণ বাইনারি ট্রি (complete binary tree) কিনা। লেভেল n-এর একটি পূর্ণ বাইনারি ট্রিতে n-1 টি পূর্ণ লেভেল থাকে, এবং লেভেল n-এ সমস্ত নোড বাম দিক থেকে ভরা থাকে। যদি ইনপুট ট্রি নিচের মতো হয় −

তবে আউটপুট হবে true, কারণ এটি একটি পূর্ণ বাইনারি ট্রি।

সমাধানের ধাপগুলো −

যদি ট্রি খালি হয়, তবে null রিটার্ন করব
একটি কিউ q বানিয়ে রুট ইনসার্ট করব
flag := true সেট করব
যখন q-তে এলিমেন্ট থাকবে
- sz := কিউর আকার
- যখন sz ০ নয়
  - node := কিউ থেকে ডিকিউ করা নোড
  - যদি নোডের বাম সাবট্রি থাকে, তবে
    - যদি flag সেট থাকে, তবে নোডের বাম সাবট্রি q-তে ইনসার্ট করব, অন্যথায় false রিটার্ন করব
  - অন্যথায় flag := false
  - যদি নোডের ডান সাবট্রি থাকে, তবে
    - যদি flag সেট থাকে, তবে নোডের ডান সাবট্রি q-তে ইনসার্ট করব, অন্যথায় false রিটার্ন করব
  - flag := false
  - sz := sz - 1
true রিটার্ন করব

নিচের ইমপ্লিমেন্টেশন দেখুন −

উদাহরণ

#include <bits/stdc++.h> using namespace std; class TreeNode{    public:    int val;    TreeNode *left, *right;    TreeNode(int data){       val = data;       left = NULL;       right = NULL;    } }; void insert(TreeNode **root, int val){    queue<TreeNode*> q;    q.push(*root);    while(q.size()){       TreeNode *temp = q.front();       q.pop();       if(!temp->left){          if(val != NULL)           temp->left = new TreeNode(val);          else           temp->left = new TreeNode(0);          return;       }else{          q.push(temp->left);       }       if(!temp->right){          if(val != NULL)           temp->right = new TreeNode(val);          else           temp->right = new TreeNode(0);          return;       }else{          q.push(temp->right);       }    } } TreeNode *make_tree(vector<int> v){    TreeNode *root = new TreeNode(v[0]);    for(int i = 1; i<v.size(); i++){       insert(&root, v[i]);    }    return root; } 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;    } }; main(){    vector<int> v = {1,2,3,4,5,6};    TreeNode *r1 = make_tree(v);    Solution ob;    cout << (ob.isCompleteTree(r1)); }

ইনপুট

{1,2,3,4,5,6}