Encontrar si un Árbol Binario es un Árbol de Búsqueda Binario [duplicar]

La respuesta proporcionada por @Dhruv es buena. Además de eso, aquí hay otra solución que funciona en O (n) tiempo.
Necesitamos hacer un seguimiento del nodo anterior en este enfoque. En cada llamada recursiva comprobamos los datos del nodo anterior con los datos del nodo actual. Si los datos del nodo actual son menores que los anteriores, devolvemos false

int isBST(node* root) {
  static node* prev  = NULL;

  if(root==NULL)
    return 1;

  if(!isBST(root->left))
    return 0;

  if(prev!=NULL && root->data<=prev->data)
    return 0;

  prev = root;
  return isBST(root->right);
}

boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max){
  if(node == null){
    return true;
  }

  boolean left  = isBinarySearchTree(node.getLeft(), min, node.getValue());
  boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

  return left && right && (node.getValue()<max) && (node.getValue()>=min);      
}

Se invita a formular observaciones. Gracias.

Creo que el segundo enfoque es correcto. El árbol puede ser atravesado de manera recursiva. En cada iteración se pueden almacenar los límites inferior y superior del subárbol actual. Si queremos comprobar el subárbol con raíz x, y los límites para el subárbol son l y h, entonces todo lo que necesitamos es comprobar que l

Esto tendrá complejidad O(n), porque comenzamos desde la raíz y cada nodo se comprueba solo una vez como raíz de algún subárbol. Además, necesitamos memoria O (h) para llamadas recursivas, donde h es la altura del árbol.

Hay algunos ejemplos anteriores usando INTEGER.MAX Y MIN No veo una razón para pasarlos y el significado de ello, corrígeme si me equivoco de alguna manera o explícame la razón.

More over binary search tree puede tener objetos que son comparados por el método compareTo o Coperator.. (de ahí Entero.MIN e Integer.MAX no encaja en ese modelo) Estoy escribiendo un código donde devuelve verdadero o falso uno tiene que llamar (root_node, true) y devolverá true si es un bst else false

void boolean isBSt( node root_node, boolean passed_root)
{

  if ( node==null){
        if ( passed_root)
        return false;
        // you have passed null pointer as 
        //root of the tree , since there is no 
        // valid start point we can throw an exception or return false      
        return true;
   }

  if( node.right !=null ) 
     if ( node.right.data <= node.data)
   return false;

  if ( node.left !=null ) 
        if ! ( node.left.data <= node.data) 
    return false;

  return ( isBST( node.right , false) && isBST( node.left, false ) )

}

Echa un vistazo a esta solución: http://preparefortechinterview.blogspot.com/2013/09/am-i-bst.html

Explica diferentes maneras y le da un método genérico y eficiente también. Espero que ayude.

Aquí hay otra Solución que usa 2 funciones auxiliares para calcular para cada nodo el valor mínimo y máximo en el subárbol usando las funciones auxiliares MinValue y MaxValue

int isBST(struct node* node)
    {
      if (node == NULL)
        return(true); 

      /* false if the max of the left is > than us */
        if (node->left!=NULL && maxValue(node->left) > node->data)
            return(false); 

      /* false if the min of the right is <= than us */
        if (node->right!=NULL && minValue(node->right) < node->data)
            return(false); 

      /* false if, recursively, the left or right is not a BST */ 
         if (!isBST(node->left) || !isBST(node->right))
           return(false); 

      /* passing all that, it's a BST */
          return(true);
    }