এখানে আমরা দেখব কিভাবে একটি বাইনারি ট্রি লেভেল অনুযায়ী সাজানো হয়েছে কি না তা পরীক্ষা করা যায়। স্তর অনুসারে সাজানো বাইনারি গাছটি নীচের মত হবে −
প্রতিটি স্তরে, নোডগুলি বাম থেকে ডানে বাছাই করা হয় এবং প্রতিটি স্তরে তার আগের স্তরের থেকে উচ্চতর মান রয়েছে৷
আমরা লেভেল অর্ডার ট্রাভার্সাল সম্পাদন করে এই সমস্যার সমাধান করতে পারি এবং বর্তমান স্তরের সর্বনিম্ন এবং সর্বাধিক উপাদানগুলির উপর নজর রাখতে পারি। পূর্ববর্তী স্তরের সর্বোচ্চ মান ধরে রাখতে অন্য একটি পরিবর্তনশীল prev_max ব্যবহার করুন। তারপর বর্তমান স্তরের সর্বনিম্ন মান এবং পূর্ববর্তী স্তরের সর্বাধিক মান পূর্ব_ম্যাক্স তুলনা করুন। যদি ন্যূনতম মান prev_max এর থেকে বেশি হয়, তাহলে ট্রিটি বর্তমান স্তর পর্যন্ত স্তর অনুসারে সাজানো হয়। তারপর prev_max আপডেট করুন এবং বর্তমান স্তরের সর্বোচ্চ মান আপডেট করুন। সমস্ত স্তর অতিক্রম না করা পর্যন্ত এটি পুনরাবৃত্তি করুন৷
৷উদাহরণ
#include <iostream>
#include <queue>
using namespace std;
class Node {
public:
int key;
Node *left, *right;
};
Node* getNode(int key) {
Node* newNode = new Node;
newNode->key = key;
newNode->left = newNode->right = NULL;
return newNode;
}
bool isLevelWiseSorted(Node* root) {
int prevMax = INT_MIN;
int min_val, max_val;
int levelSize;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
levelSize = q.size();
min_val = INT_MAX;
max_val = INT_MIN;
while (levelSize > 0) {
root = q.front();
q.pop();
levelSize--;
min_val = min(min_val, root->key);
max_val = max(max_val, root->key);
if (root->left)
q.push(root->left);
if (root->right)
q.push(root->right);
}
if (min_val <= prevMax)
return false;
prevMax = max_val;
}
return true;
}
int main() {
Node* root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->right->left = getNode(6);
root->right->right = getNode(7);
if (isLevelWiseSorted(root))
cout << "Tree is levelwise Sorted";
else
cout << "Tree is Not levelwise sorted";
} আউটপুট
Tree is level wise Sorted
