Si el recorrido en orden de un árbol binario produce una salida ordenada, ¿es el árbol un árbol de búsqueda binario?

Question

Dado un árbol de búsqueda binario, es fácil ver que el recorrido en orden devuelve los valores del conjunto subyacente en orden (según el comparador que configuró el árbol de búsqueda binario).

Mi pregunta se refiere a la inversa de esta afirmación: si tenemos un árbol binario con el recorrido de entrada que produce una salida ordenada, ¿implica esto que el árbol es un árbol de búsqueda binario?

Answer 1

Sí -- la condición del árbol de búsqueda se satisfará en cada nodo, porque por definición de inorden cada valor en su subárbol izquierdo será visitado antes (y por lo tanto será más pequeño) que el valor en el nodo, y de manera similar para el subárbol derecho.