Referência: Esta pergunta foi feita na entrevista da @MS SDE, na 3ª rodada. E não é um problema de lição de casa. Eu também dei um pensamento e mencionei minha abordagem abaixo.

Questão: Modifique um BST para que ele se torne o mais equilibrado possível. É desnecessário mencionar que você deve fazê-lo da maneira mais eficiente possível.

Dica: Entrevistador disse que esta é uma questão lógica, se você pensar de forma diferente, você receberá a resposta. Nenhuma codificação difícil envolvida.
-> Dito isto, eu não acho que ele estava esperando que eu apontasse para AVL / RB Trees.

Minha solução: Eu propus que, eu faria em ordem de travessia da árvore, pegue o elemento do meio como raiz da nova árvore (vamos chamá-lo de nova raiz). Em seguida, vá para a parte esquerda do elemento do meio, pegue seu elemento do meio como raiz da subárvore esquerda da raiz nova da árvore. Da mesma forma, para a parte direita. Fazendo isso de forma recursiva, você obterá o BST balanceado ideal.

Por que estou postando aqui: Mas ele não estava satisfeito com a resposta :( Então, há realmente uma maneira de fazer isso sem ir para pesos / estratégia de colorir RB, ou ele estava apenas brincando comigo? Por favor, coloque em seus pensamentos de especialistas.

Duplicado? Não! Eu sei que tem issoquestão mas a solução proposta pelo solicitante é muito complicada, e outra se refere às árvores AVL.