algorithm
Проверьте, нет ли дерева BST или нет.

Если заданное дерево ввода следует за свойством дерева двоичного поиска или нет

Например

если вход:

Выход должен быть ложным:

Поскольку 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. Чтобы проверить, упорядочена ли последовательность порядка, помните значение ранее посещаемого узла и сравнивайте его с текущим узлом.