Esta pregunta ya tiene una respuesta aquí:

Hoy tuve una entrevista en la que me pidieron que escribiera un programa que toma un Árbol binario y devuelve verdadero si también es un Árbol de búsqueda binario, de lo contrario es falso.

Mi Enfoque 1: realice un recorrido transversal en orden y almacene los elementos en tiempo O (n). Ahora escanee a través de la matriz / lista de elementos y verifique si el elemento está en ith El índice es mayor que el elemento en (i + 1)th índice. Si se encuentra una condición de este tipo, devuelva falso y salga del bucle. (Esto lleva tiempo O (n)). Al final devuelve verdadero.

Pero este caballero quería que yo proporcionara una solución eficiente. Lo intenté pero no tuve éxito, porque para encontrar si es un BST, tengo que verificar cada nodo.

Además me estaba señalando que pensara en la recursión. Mi Enfoque 2: Un BT es un BST si para cualquier nodo N N-> izquierdo es <N y N-> derecho> N, y el sucesor en orden del nodo izquierdo de N es menor que N y el sucesor en orden El nodo derecho de N es mayor que N y los subárboles izquierdo y derecho son BST.

Pero esto va a ser complicado y el tiempo de ejecución no parece ser bueno. Por favor ayuda si conoces alguna solución óptima.