algorithm
Compruebe si un árbol es BST o no

Si un árbol de entrada dado sigue una propiedad del árbol de búsqueda binaria o no

Por ejemplo

si la entrada es:

La salida debe ser falsa:

Como 4 en el subárbol izquierdo es mayor que el valor raíz (3)

Si la entrada es:

La salida debe ser verdadera

Algoritmo para verificar si un árbol binario dado es BST

Un árbol binario es BST si satisface cualquiera de las siguientes condiciones:

1. Esta vacio
2. No tiene subárboles.
3. Para cada nodo x en el árbol, todas las claves (si las hay) en el subárbol izquierdo deben ser menores que la clave (x) y todas las claves (si las hay) en el subárbol derecho deben ser mayores que la clave (x).

Entonces, un algoritmo recursivo directo sería:

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)

El algoritmo recursivo anterior es correcto pero ineficiente, ya que atraviesa cada nodo varios tiempos.

Otro enfoque para minimizar las visitas múltiples de cada nodo es recordar los valores mínimos y máximos posibles de las claves en el subárbol que estamos visitando. Deje que el valor mínimo posible de cualquier clave sea K_MIN y el valor máximo sea K_MAX . Cuando comenzamos desde la raíz del árbol, el rango de valores en el árbol es [K_MIN,K_MAX] . Deje que la clave del nodo raíz sea x . Luego, el rango de valores en el subárbol izquierdo es [K_MIN,x) y el rango de valores en el subárbol derecho es (x,K_MAX] . Usaremos esta idea para desarrollar un algoritmo más eficiente.

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)

Se llamará inicialmente como:

is_BST(my_tree_root,KEY_MIN,KEY_MAX)

Otro enfoque será hacer un recorrido ordenado del árbol binario. Si el recorrido inorder produce una secuencia ordenada de claves, entonces el árbol dado es un BST. Para verificar si la secuencia inorder está ordenada, recuerde el valor del nodo visitado anteriormente y compárelo con el nodo actual.