algorithm
Controlla se un albero è BST o no

Se una determinata struttura di input segue la proprietà dell'albero di ricerca binaria o meno

Per esempio

se l'input è:

L'output dovrebbe essere falso:

Poiché 4 nel sottoalbero sinistro è maggiore del valore radice (3)

Se l'input è:

L'output dovrebbe essere vero

Algoritmo per verificare se un dato albero binario è BST

Un albero binario è BST se soddisfa una delle seguenti condizioni:

1. È vuoto
2. Non ha sotto-canali
3. Per ogni nodo x nell'albero tutte le chiavi (se presenti) nell'albero secondario sinistro devono essere inferiori alla chiave (x) e tutte le chiavi (se presenti) nell'albero secondario destro devono essere maggiori della chiave (x).

Quindi un algoritmo ricorsivo diretto sarebbe:

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)

L'algoritmo ricorsivo di cui sopra è corretto ma inefficiente, perché attraversa ogni nodo più volte.

Un altro approccio per minimizzare le visite multiple di ciascun nodo è quello di ricordare i valori minimo e massimo possibili delle chiavi nella sottostruttura che stiamo visitando. Lascia che il valore minimo possibile di qualsiasi chiave sia K_MIN e il valore massimo sia K_MAX . Quando iniziamo dalla radice dell'albero, l'intervallo di valori nell'albero è [K_MIN,K_MAX] . Lascia che la chiave del nodo radice sia x . Quindi l'intervallo di valori nella sottostruttura di sinistra è [K_MIN,x) e l'intervallo di valori nella sottostruttura di destra è (x,K_MAX] . Useremo questa idea per sviluppare un algoritmo più efficiente.

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)

Inizialmente sarà chiamato come:

is_BST(my_tree_root,KEY_MIN,KEY_MAX)

Un altro approccio sarà fare l'attraversamento inorder dell'albero binario. Se l'inorder traversal produce una sequenza ordinata di chiavi, allora l'albero dato è un BST. Per verificare se la sequenza in ordine è ordinata, ricordare il valore del nodo visitato in precedenza e confrontarlo con il nodo corrente.