El único enfoque estrictamente correcto que se me ocurre es utilizar la programación dinámica para una solución O (nh), donde n es el número de nodos yh es la altura del árbol. Los dos parámetros de nuestros estados son (índice de nodo, altura requerida). Luego, como nuestra transición, si la altura requerida es igual al máximo de los dos lados y las alturas están dentro de uno, estamos listos para ir y podemos dejar que los niños decidan cómo equilibrarse (llámelos con su altura real). Si no, elija un lado para aumentar a la altura requerida y aumente el otro a ese menos uno. Aquí hay dos opciones, pero esto resulta ser intrascendente con la memorización. El número total de alturas posibles está limitado por h, por lo que, en general, si recordamos tenemos O (nh).
Al principio, puede parecer que aumentar la altura de un árbol más alto es estrictamente mejor que aumentar la altura del árbol más bajo, pero esto no es cierto. Compare agregar una altura a un árbol de Fibonacci con agregar dos alturas a un árbol completo. El primero requiere un número exponencial de adiciones en h, y el último solo requiere un número lineal de adiciones. Esta heurística, como muchas heurísticas codiciosas, no tiene en cuenta los lazos, lo que indica aún más su insuficiencia.