C++ में बाइनरी ट्री लेवल-वाइज क्रमबद्ध है या नहीं जांचें

समस्या विवरण

जांचें कि बाइनरी ट्री लेवल-वाइज क्रमबद्ध है या नहीं। प्रत्येक लेवल में नोड्स बाएं से दाएं क्रमबद्ध हों और प्रत्येक लेवल के मान पिछले लेवल से बड़े हों।

एल्गोरिदम (लेवल ऑर्डर ट्रैवर्सल)

1. क्यू का उपयोग करके लेवल ऑर्डर ट्रैवर्सल
2. प्रत्येक लेवल के लिए न्यूनतम (min_val) और अधिकतम (max_val) ट्रैक करें
3. prev_max = पिछले लेवल का अधिकतम
4. यदि min_val ≤ prev_max → लेवल-वाइज क्रमबद्ध नहीं
5. prev_max = max_val अपडेट करें

उदाहरण कोड

#include <iostream>
#include <queue>
#include <climits>
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;
    queue q;
    q.push(root);
    
    while (!q.empty()) {
        int levelSize = q.size();
        int minVal = INT_MAX, maxVal = INT_MIN;
        
        while (levelSize > 0) {
            root = q.front(); q.pop();
            levelSize--;
            minVal = min(minVal, root->key);
            maxVal = max(maxVal, root->key);
            if (root->left) q.push(root->left);
            if (root->right) q.push(root->right);
        }
        
        if (minVal <= prevMax) return false;
        prevMax = maxVal;
    }
    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";
    return 0;
}

आउटपुट

Tree is level wise Sorted