与えられた木が二分探索木（BST）かどうかを判定するC++プログラム

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

• あるノードの左部分木には、そのノードのキーより小さいキーを持つノードだけが含まれます。

• あるノードの右部分木には、そのノードのキーより大きいキーを持つノードだけが含まれます。

• 左右どちらの部分木も、それ自体が二分探索木でなければなりません。

アルゴリズム

この判定は、各ノードが取りうるキー値の範囲（最小値〜最大値）を引数として渡しながら木を再帰的にたどることで実現します。ノードの値が許容範囲から外れた時点で、その木はBSTではないと判断できます。

開始
　　関数 BSTUtil()
　　　　ノードがNULLの場合
　　　　　　1を返す。
　　　　ノードのデータが最小値未満または最大値超過の場合
　　　　　　0を返す。
　　　　左右の部分木を再帰的に走査する。
終了。

サンプルコード

#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 Tree is a BST"<<endl;
    else
       cout<<"The Given 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 Tree is a BST"<<endl;
    else
       cout<<"The Given Tree is not a BST"<<endl;
    return 0;
}

実行結果

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

最初の木では、ノード6の右の子が4（6より小さい値）になっているため、「右の子は親より大きい」というBSTの条件を満たさず、正しく「not a BST」と判定されます。一方、2番目の木はすべてのノードが条件を満たしているため、正当なBSTとして認識されます。このように、範囲チェックによる再帰的な探索を行えば、木全体が二分探索木の性質を満たしているかどうかを効率的に確認できます。