Algoritmos y Estructuras de Datos - VJ1215

Ejemplo de error en el ejercicio 2.h del tema 3

La siguiente solución no es correcta, piensa por qué.

bool Conjunto::esArbolBinarioDeBusqueda(Nodo * n) const {
   if (n->izquierdo != nullptr)
      if (n->izquierdo->dato > n->dato || ! esArbolBinarioDeBusqueda(n->izquierdo))
	 return false;
   if (n->derecho != nullptr)
      if (n->derecho->dato < n->dato || ! esArbolBinarioDeBusqueda(n->derecho))
	 return false;
   return true;
}   

bool Conjunto::esArbolBinarioDeBusqueda() const {
   if (raiz == nullptr)
      return true;
   return esArbolBinarioDeBusqueda(raiz);
}

¿Por qué es incorrecta?

La solución anterior solamente verifica que el dato de cada nodo es mayor o igual que el de su hijo izquierdo (si existe) y menor o igual que el de su hijo derecho (si existe): eso no basta para ser un árbol binario de búsqueda, el dato de cada nodo debe ser mayor o igual que todos los de su subárbol izquierdo y menor o igual que todos los de su subárbol derecho. En el siguiente ejemplo, 30 es mayor que 20 y 5 es menor que 30, pero no es un árbol binario de búsqueda porque 5 es menor que 20.