Un nodo de árbol binario tiene un valor y hasta dos hijos. La mayoría de los problemas de árboles tienen la misma forma: responde a la pregunta para el subárbol izquierdo, respóndela para el derecho y combina las dos respuestas en el nodo. El árbol vacío es el caso base.
Algunas preguntas tratan en cambio sobre niveles. El recorrido en anchura las resuelve: guarda los nodos de un nivel, procésalos todos y reúne sus hijos como siguiente nivel.
Un árbol binario de búsqueda añade una regla: todo lo que está a la izquierda de un nodo es menor y todo lo que está a la derecha es mayor. Comprobarlo exige más que un nodo y sus hijos, así que pasa el rango permitido hacia abajo sobre la marcha.
La recursión cuesta O(h) de espacio de pila, donde h es la altura. Prueba un árbol vacío, un nodo, un árbol inclinado hacia un lado, valores negativos y, en Java, sumas o cotas que superan el rango de int. En las pruebas, los árboles se escriben nivel a nivel con null para un hijo que falta.
Cada nodo añade un nivel al más profundo de sus dos subárboles.