Referencia: Me hicieron esta pregunta @ MS SDE entrevista, 3ra ronda. Y no es un problema de tarea. También lo pensé y mencioné mi enfoque a continuación.

Pregunta: Modifique un BST para que esté lo más equilibrado posible. No hace falta mencionar que debes hacerlo lo más eficiente posible.

Insinuación: El entrevistador dijo que esta es una pregunta lógica, si piensas de manera diferente obtendrás la respuesta. No requiere codificación complicada.
-> Habiendo dicho eso, no creo que él estuviera esperando que apunte a los árboles AVL / RB.

Mi solución: Propuse que, haría un recorrido ordenado del árbol, tomaría el elemento central como la raíz del nuevo árbol (llamémoslo nueva raíz). Luego vaya a la parte izquierda del elemento central, tome su elemento central como raíz del subárbol izquierdo de la raíz nueva arraigada en el árbol. Del mismo modo hacer por parte correcta. Hacer esto de forma recursiva dará el BST óptimo equilibrado.

Por qué lo estoy publicando aquí: Pero no estaba satisfecho con la respuesta :( Entonces, ¿existe realmente una manera de hacerlo sin ir por la estrategia de colorear pesos / RB, o simplemente estaba jugando conmigo? Por favor, póngalo en sus pensamientos de expertos.

¿Duplicar? ¡No! Se que hay estopregunta pero la solución propuesta por el solicitante es demasiado complicada, y otra habla de árboles AVL.