二分木がBST（二分探索木）であるかどうかを判定するC++プログラム

二分探索木（Binary Search Tree：BST）とは、次の3つの性質を満たす二分木データ構造のことです。

• あるノードの左部分木には、そのノードのキーよりも小さいキーを持つノードのみが含まれる。
• あるノードの右部分木には、そのノードのキーよりも大きいキーを持つノードのみが含まれる。
• 左部分木と右部分木のそれぞれも、必ず二分探索木でなければならない。

アルゴリズム

BST判定は、各ノードに「取り得る値の範囲（最小値・最大値）」を渡しながら再帰的に木をたどることで実現できます。手順は以下の通りです。

Begin
    function BSTUtill()
        ノードがNULLと等しい場合
            1 を返す。
        ノードのデータが最小値未満または最大値より大きい場合
            0 を返す。
        左部分木と右部分木を再帰的にたどる。
End.

この方法では、単に親子関係だけを見るのではなく、ルートから各ノードまでの経路全体で妥当な値の範囲を更新していくため、正確にBSTかどうかを判定できます。

サンプルコード

以下は、C++で二分木がBSTであるかどうかを判定するプログラムの例です。INT_MIN と INT_MAX を初期範囲として利用しています。

#include <iostream>
#include <cstdlib>
#include <climits>
using namespace std;
struct n {
    int d;
    n* l;
    n* r;
};
int BSTUtil(n* node, int min, int max);
int isBST(n* node) {
    return(BSTUtil(node, INT_MIN, INT_MAX));
}
int BSTUtil(struct n* node, int min, int max) {
    if (node==NULL)
        return 1;
    if (node->d < min || node->d > max)
        return 0;
        return BSTUtil(node->l, min, node->d - 1) && BSTUtil(node->r, node->d + 1, max);
}
n* newN(int d) {
    n* nod = new n;
    nod->d = d;
    nod->l = NULL;
    nod->r = NULL;
    return nod;
}
int main() {
    n *root = newN(7);
    root->l = newN(6);
    root->r = newN(10);
    root->l->l = newN(2);
    root->l->r = newN(4);
    if (isBST(root))
        cout<<"The Given Binary Tree is a BST"<<endl;
    else
        cout<<"The Given Binary Tree is not a BST"<<endl;
        n *root1 = newN(10);
        root1->l = newN(6);
        root1->r = newN(11);
        root1->l->l = newN(2);
        root1->l->r = newN(7);
        if (isBST(root1))
            cout<<"The Given Binary Tree is a BST"<<endl;
        else
            cout<<"The Given Binary Tree is not a BST"<<endl;
        return 0;
}

出力結果

The Given Binary Tree is not a BST
The Given Binary Tree is a BST

解説

最初の例では、ルート7に対して左の子6、さらにその下に4というノードがあります。4は6より小さいため一見問題ないように見えますが、ルート7の左部分木内にあるべき値の範囲（7未満）の中でも、6の右側に配置できるのは6以上7未満の値のみです。この制約により、この木はBSTではないと判定されます。

一方、2番目の例では、すべてのノードが「左の子 ＜ 親 ＜ 右の子」という条件と、各部分木における値の範囲制約を満たしているため、BSTであると判定されます。

このアルゴリズムの計算量は、木の各ノードを一度ずつ訪問するため O(n)、再帰呼び出しによるスタックの深さは木の高さに依存し、最悪の場合（偏った木）で O(n) の空間計算量となります。