algorithm
ツリーがBSTかどうかを確認する

指定された入力ツリーがバイナリ検索ツリーのプロパティに従っているかどうか

例えば

入力が次の場合：

出力はfalseでなければなりません：

左のサブツリーの4が根の値（3）より大きいため、

入力が次の場合：

出力は真でなければならない

与えられたバイナリツリーがBSTかどうかをチェックするアルゴリズム

バイナリツリーは、次のいずれかの条件を満たす場合はBSTです。

1. それは空です
2. サブツリーはありません
3. ツリー内のすべてのノードxに対して、左のサブツリーのすべてのキー（存在する場合）はキー（x）より小さくなければならず、右のサブツリーのすべてのキー（存在する場合）はキー（x）より大きくなければなりません。

したがって、簡単な再帰アルゴリズムは次のようになります。

is_BST(root):
  if root == NULL:
   return true

  // Check values in left subtree
  if root->left != NULL:
    max_key_in_left = find_max_key(root->left)
    if max_key_in_left > root->key:
        return false

  // Check values in right subtree
  if root->right != NULL:
    min_key_in_right = find_min_key(root->right)
    if min_key_in_right < root->key:
        return false

  return is_BST(root->left) && is_BST(root->right)

上記の再帰的アルゴリズムは、各ノードを複数回通過するため、正確ではあるが非効率的である。

各ノードの多重訪問を最小限にする別のアプローチは、訪問しているサブツリー内のキーの可能な最小値および最大値を記憶することである。任意のキーの最小値をK_MIN 、最大値をK_MAXます。ツリーのルートから始めると、ツリー内の値の範囲は[K_MIN,K_MAX]です。ルートノードのキーをx 。次に、左のサブツリーの値の範囲は[K_MIN,x)あり、右のサブツリーの値の範囲は(x,K_MAX]です。

is_BST(root, min, max):
    if root == NULL:
        return true

    // is the current node key out of range?
    if root->key < min || root->key > max:
        return false

    // check if left and right subtree is BST
    return is_BST(root->left,min,root->key-1) && is_BST(root->right,root->key+1,max)

それは当初、次のように呼ばれます：

is_BST(my_tree_root,KEY_MIN,KEY_MAX)

別の方法は、バイナリツリーのインオーダートラバーサルを行うことです。インオーダートラバーサルがソートされたキーシーケンスを生成する場合、指定されたツリーはBSTです。インオーダーシーケンスがソートされているかどうかをチェックするには、以前に訪問したノードの値を覚えて、それを現在のノードと比較します。