Considere que os números na tabela acima representem uma ...

a inserção na árvore binária é sempre na próxima posição, ou seja, posição n+1! Porém é preciso ir subindo e trocando o número inserido caso ele seja menor que os de mais. Isso acaba sendo no pior caso log n pq o número inserido pode virar raiz. Resumindo, as dicas acima me fizeram chegar na seguinte sequencia -> 113 - 172 - 157 - 189 - 245 - 181 - 217 - 264 - 194. Assim, trocando o índice 3 pelo 6 na sequencia errada fica o 157 na terceira posição e o 181 na sexta. Boa questão!!

Para resolver essa questão precisamos lembrar que em uma árvore binária, valores maiores vão para nós à direita e valores menores para nós à esquerda.

Logo, refazendo a busca temos:

1 - 194 > 113 - Direita

2 - 194 < 264 - Esquerda

3 - 194 > 181 - Direita

4 - 194 > 172 - Direita

5 - 194 < 245 - Esquerda

6 - 194 > 157 - Direita

7 - 194 < 217 - Esquerda

8 - 194 > 189 - Direita

9 - 194 = 194 - Achou

Perceba que ocorre um erro no movimento 3 para o 4, pois quando o 181 é visitado ele vai para direita e na direita do 181 só deveriam existir nós maiores que ele, contudo o nó seguinte é o 172 (menor que 181), logo, a direção tomada no nó 3 foi errada.

A solução então é pensar qual nó poderíamos trocar por 181 para que o caminho fique correto. Dentre as opções só temos uma com o 3 e é a resposta correta.

245 seria então nó raiz nesse caso certo?

Teríamos que pressupor que a estratégia estava em ordem e não em pré ordem ou pós ordem?