配列が高さnのBSTを表せるかどうかをC++で判定する方法

サイズnの配列が与えられたとき、その配列が高さnの二分探索木（BST）を表すことができるかどうかを判定する問題について解説します。ここで「高さn」とは、根から葉までの最長パスがn個のノードで構成されることを意味し、つまり配列の各要素が木の各レベルに1つずつ対応することを指します。

問題の理解

BSTのルールに従って要素を挿入していくとき、配列の順序通りに挿入した結果、高さがちょうどn（要素数と同じ）になるかどうかを確認します。これは、配列の各要素が前の要素の左または右の子として挿入され、一度も同じレベルに複数のノードが配置されないことを意味します。

例として以下の2つの配列を考えます：

• {50, 20, 9, 25, 10} → 無効
• {50, 30, 20, 25, 10} → 有効

最初の配列では、25 が 20 の右の子として挿入される際、9 の右部分木に入るべきところを 20 の右部分木に入ってしまい、高さが5になりません。2番目の配列では、各要素が前の要素の左または右の子として正しく連なり、高さ5のBSTが構築できます。

アルゴリズム：範囲ベースのアプローチ

実際に木を構築せず、配列を1回走査するだけで判定できます。各ノードには「許容される値の範囲（最小値・最大値）」があり、この範囲を更新しながら検証します。

1. 初期値として min = INT_MIN、max = INT_MAX を設定
2. 配列の2番目の要素から順に処理：
   • 現在の要素 arr[i] が前の要素 arr[i-1] より大きい場合（右の子）:
     • arr[i-1] < arr[i] < max を満たす必要がある
     • 条件を満たせば min = arr[i-1] を更新
   • 現在の要素が前の要素より小さい場合（左の子）:
     • min < arr[i] < arr[i-1] を満たす必要がある
     • 条件を満たせば max = arr[i-1] を更新
   • どちらの条件も満たさない場合、その要素は新しいレベルに挿入されることになるため、高さnのBSTとしては無効
3. 全要素を処理できれば有効、途中で失敗すれば無効

C++実装例

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

// 配列が高さnのBSTを表せるか判定
// 表せるなら true、表せないなら false を返す
bool canRepresentBSTOfHeightN(int arr[], int n) {
    int minVal = INT_MIN;
    int maxVal = INT_MAX;
    
    for (int i = 1; i < n; i++) {
        // 右の子として挿入されるケース
        if (arr[i] > arr[i - 1] && arr[i] > minVal && arr[i] < maxVal) {
            minVal = arr[i - 1];  // 下限を更新
        }
        // 左の子として挿入されるケース
        else if (arr[i] < arr[i - 1] && arr[i] > minVal && arr[i] < maxVal) {
            maxVal = arr[i - 1];  // 上限を更新
        }
        // どちらの条件も満たさない → 無効
        else {
            return false;
        }
    }
    return true;
}

int main() {
    int validArr[]   = {50, 30, 20, 25, 10};
    int invalidArr[] = {50, 20, 9, 25, 10};
    int n = sizeof(validArr) / sizeof(validArr[0]);
    
    cout << "有効な配列: "
         << (canRepresentBSTOfHeightN(validArr, n) ? "高さ " + to_string(n) + " のBSTとして有効"
                                                 : "高さ " + to_string(n) + " のBSTとして無効")
         << endl;
    
    cout << "無効な配列: "
         << (canRepresentBSTOfHeightN(invalidArr, n) ? "高さ " + to_string(n) + " のBSTとして有効"
                                                    : "高さ " + to_string(n) + " のBSTとして無効")
         << endl;
    
    return 0;
}

実行結果

有効な配列: 高さ 5 のBSTとして有効
無効な配列: 高さ 5 のBSTとして無効

解説のポイント

• 時間計算量: O(n) — 配列を1回走査するだけ
• 空間計算量: O(1) — 追加のデータ構造を使用しない
• このアルゴリズムは「配列の順序通りにBSTへ挿入したとき、高さがnになるか」を判定します。一般的な「配列がBSTの前順巡回結果かどうか」を判定する問題とは異なる点に注意してください。

よくある間違い

• 元のサンプルコードでは戻り値の真偽が逆になっていました（無効時に true を返す）。上記のコードでは修正済みです。
• 等しい値が含まれる場合の扱い（左に入れるか右に入れるか）は仕様によります。上記コードでは < と > で厳密に判定しています。