C++で二分木がレベルごとにソートされているかを確認する方法

本記事では、二分木（バイナリツリー）がレベルごとにソートされているかどうかを判定する方法を解説します。レベルごとにソートされた二分木とは、以下のような構造を持つ木のことです。

このような二分木では、各レベル内でノードが左から右へ向かって昇順に並んでおり、さらに下のレベルほど、その上のレベルより大きな値を持つという特徴があります。

アルゴリズムの考え方

この問題は、レベル順走査（幅優先探索：BFS）を用いることで効率的に解決できます。手順は以下の通りです。

1. キューを使ってレベル順にノードを走査します。
2. 現在のレベルの最小値（min_val）と最大値（max_val）を記録します。
3. 前のレベルの最大値を保持する変数 prevMax を用意します。
4. 現在のレベルの最小値が prevMax 以下であれば、レベルごとのソート条件を満たしていないため false を返します。
5. 条件を満たしていれば prevMax を現在のレベルの最大値で更新し、次のレベルへ進みます。

すべてのレベルの走査が完了すれば、その二分木はレベルごとにソートされていると判定できます。

C++による実装例

#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

計算量について

このアルゴリズムでは、各ノードを一度だけ訪問するため、時間計算量は O(n)（n はノード数）となります。また、キューには最大で1レベル分のノードしか保持されないため、空間計算量も最悪ケースで O(n) です。二分木の幅が狭い場合（バランスの取れた木など）は、O(log n) 程度に抑えられることもあります。