Kiểm tra cây nhị phân có sắp xếp theo level C++

Cây nhị phân level-wise sorted: mỗi level các nút tăng dần trái→phải, và mọi nút level sau đều lớn hơn level trước.

Giải thuật (BFS)

1. Duyệt level-order (BFS) với queue
2. Mỗi level: tìm min_val, max_val
3. Kiểm tra min_val > prev_max (max của level trước)
4. Cập nhật prev_max = max_val

Ví dụ minh họa

#include <iostream>
#include <queue>
#include <climits>
using namespace std;

class Node {
public:
    int key;
    Node *left, *right;
};

Node* getNode(int key) {
    Node* n = new Node;
    n->key = key; n->left = n->right = NULL;
    return n;
}

bool isLevelWiseSorted(Node* root) {
    if (!root) return true;
    queue<Node*> q;
    q.push(root);
    int prevMax = INT_MIN;
    
    while (!q.empty()) {
        int levelSize = q.size();
        int minVal = INT_MAX, maxVal = INT_MIN;
        
        while (levelSize--) {
            Node* cur = q.front(); q.pop();
            minVal = min(minVal, cur->key);
            maxVal = max(maxVal, cur->key);
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->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);
    
    cout << (isLevelWiseSorted(root) ? "Cay level-wise sorted" : "Cay KHONG level-wise sorted");
}

Kết quả

Cay level-wise sorted