Problema número 298

¿Es un árbol binario de búsqueda?

Tiempo máximo: 2,000-5,000 sMemoria máxima: 4096 KiB

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.

Un árbol que no es de búsqueda y otro que sí lo es

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