¿Es un árbol binario de búsqueda?
Un árbol binario de búsqueda es un árbol binario cuyos nodos almacenan claves (y valores asociados a esas claves) que se mantienen ordenadas de la siguiente manera: la raíz del árbol contiene una clave que es estrictamente mayor que todas las claves almacenadas en el hijo izquierdo y estrictamente menor que todas las claves almacenadas en el hijo derecho; además, ambos hijos son árboles binarios de búsqueda.
De los siguientes árboles (con números enteros como claves) solamente el de la derecha es un árbol binario de búsqueda.
Dado un árbol binario, el problema consiste en decidir si es o no un árbol binario de búsqueda.
Entrada
La entrada comienza con el número de casos que vienen a continuación. Cada caso de prueba consiste en una línea con la descripción de un árbol binario: primero aparece su raíz (un entero no negativo), y a continuación la descripción del hijo izquierdo y después la del hijo derecho. El número −1 indica el árbol vacío. Los árboles nunca contendrán más de 4.000 nodos.
Salida
Para cada árbol se escribirá SI si el árbol es un árbol binario de búsqueda y NO si no lo es.
Entrada de ejemplo
4 1 2 4 -1 -1 5 -1 -1 3 -1 6 -1 -1 5 4 1 -1 -1 -1 8 6 -1 -1 9 -1 -1 -1 2 2 -1 -1 -1
Salida de ejemplo
NO SI SI NO