【C++】配列が二分探索木（BST）の先行順トラバーサルとして有効かどうかを判定する方法

配列に格納された要素のリストが与えられたとき、その要素列が二分探索木（BST）の先行順トラバーサル（プレオーダー走査）として成立するかどうかを判定する問題について解説します。

例えば、数列が {40, 30, 35, 80, 100} の場合、対応する二分探索木は次のようになります。

スタックを使った効率的な解法

この問題は、スタックを1つ使うことで線形時間 O(n) で解くことができます。基本的な考え方は、「先行順走査では親ノードが子ノードより先に現れる」という性質を利用し、スタックで祖先ノードの候補を管理するというものです。

具体的には、以下の手順に従います。

• 空のスタックを定義する
• 変数 root を負の無限大（INT_MIN）で初期化する
• 先行順の各要素に対して、次の処理を行う：
  • 現在の要素が root より小さい場合は、BST の条件に反するため false を返す
  • 現在の要素がスタックのトップより大きい間、スタックから要素を取り除き続け、最後に取り除いた要素を新しい root とする（これは右側の部分木へ移動したことを意味する）
  • 現在の要素をスタックにプッシュする

すべての要素を処理して問題がなければ、その配列は有効な BST の先行順トラバーサルであると言えます。

サンプルコード

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

bool isValidPreorder(int pre[], int n) {
    stack<int> stk;
    int root = INT_MIN;
    for (int i = 0; i < n; i++) {
        // 現在の要素が直近の親より小さい場合は不正
        if (pre[i] < root)
            return false;
        // スタックトップより大きい間、親を更新
        while (!stk.empty() && stk.top() < pre[i]) {
            root = stk.top();
            stk.pop();
        }
        stk.push(pre[i]);
    }
    return true;
}

int main() {
    int pre[] = {40, 30, 35, 80, 100};
    int n = sizeof(pre) / sizeof(pre[0]);
    if (isValidPreorder(pre, n))
        cout << "この配列はBSTの先行順トラバーサルとして有効です";
    else
        cout << "この配列はBSTの先行順トラバーサルとして無効です";
}

実行結果

この配列はBSTの先行順トラバーサルとして有効です

計算量

• 時間計算量： O(n) — 各要素は最大でも1回プッシュされ、1回ポップされるためです。
• 空間計算量： O(n) — 最悪ケース（昇順に並んだ配列など）では、すべての要素がスタックに積まれる可能性があります。

このように、スタックを活用することで再帰を使わずに、配列が二分探索木の先行順トラバーサルとして妥当かどうかを簡潔かつ高速に判定できます。