A travessia InOrder é uma das três formas populares de atravessar uma estrutura de dados em árvore binária, sendo as outras duas a preOrder e a postOrder. Durante o algoritmo de travessia na ordem, a sub-árvore esquerda é explorada primeiro, seguida pela raiz, e finalmente os nós na sub-árvore direita. Você começa a travessia pela raiz e depois vai para o nó esquerdo, depois novamente vai para o nó esquerdo até chegar a um nó de folha. Nesse momento, você imprime o valor do nó ou marca-o visitado e se move para a sub-árvore direita. Continuando o mesmo algoritmo até que todos os nós da árvore binária sejam visitados. A travessia InOrder também é conhecida como o algoritmo de travessia de nó-esquerda-direita ou de travessia de raiz-esquerda-direita ou LNR.
Semelhante ao algoritmo de preOrder, também é um algoritmo de profundidade-primeira porque explora a profundidade de uma árvore binária antes de explorar os irmãos. Como é um dos algoritmos fundamentais de árvore binária é bastante popular em entrevistas de programação.
Estes algoritmos de travessia também são a base para aprender algoritmos de árvore binária mais avançados, portanto todo programador deve aprender, entender e saber como implementar algoritmos de ordem e outros algoritmos de travessia.
A maneira mais fácil de implementar o algoritmo de travessia inOrder em Java ou qualquer linguagem de programação é usando recursividade. Como a árvore binária é uma estrutura de dados recursiva, a recursividade é a escolha natural para resolver um problema baseado em árvores. O método inOrder() na classe BinaryTree implementa a lógica para atravessar uma árvore binária usando recursion.
Do ponto de vista de Interview, o InOrder traversal é extremamente importante porque também imprime nós de uma árvore de busca binária na ordem ordenada, mas somente se a árvore dada for uma árvore de busca binária. Se você lembrar, em BST, o valor dos nós na sub-árvore esquerda é menor que a raiz, e os valores dos nós na sub-árvore direita são maiores que a raiz. O Em ordem traversal significa literalmente EM ordem, ou seja, notas são impressas na ordem ou ordenadas.
Btw, mesmo que esses três algoritmos (pré-ordem, em ordem, e pós-ordem) sejam algoritmos populares de traversal de árvore binária, mas não são os únicos. Você também tem outras formas de atravessar uma árvore binária, e.g., nível de ordem de atravessamento (Veja Estrutura de Dados e Algoritmos: Mergulho Profundo).

O algoritmo recursivo para implementar o InOrder traversal de uma árvore binária

O algoritmo recursivo de inorder traversal é muito simples. Você só precisa chamar o método inOrder() da classe BinaryTree na ordem em que você quer visitar a árvore. O mais importante é incluir o caso base, que é a chave para qualquer algoritmo recursivo.
Por exemplo, neste problema, o caso base é você chegar ao nó folha e não há mais nó a explorar, naquele ponto do tempo a recursividade começa a diminuir. Aqui estão os passos exatos para atravessar a árvore binária usando InOrder traversal:

1. visitar nó esquerdo
2. valor de impressão da raiz
3. visitar nó direito

e aqui está o código de exemplo para implementar este algoritmo usando recursividade em Java:
>Similiar ao método preOrder() no último exemplo, existe outro método inOrder() que expõe a travessia inOrder ao público e chama este método privado que realmente executa a travessia InOrder.
Esta é a maneira padrão de escrever um método recursivo que leva entrada, facilita para um cliente chamar o método.
public void inOrder() { inOrder(root);}
Você pode ver que começamos com root e depois chamamos recursivamente o método inOrder() com nó.esquerda, o que significa que estamos descendo na sub-árvore esquerda até atingirmos o nó == nulo, o que significa que o último nó era um nó folha.
Neste momento, o método inOrder() irá retornar e executar a próxima linha, que imprime o nó.data. Depois disso é novamente recursiva a chamada inOrder() com node.right, que iniciará o mesmo processo novamente.
Pode também verificar os cursos Estrutura de Dados e Algoritmos Parte 1 e 2 em Pluralsight para aprender mais sobre algoritmos e como projetar seus próprios algoritmos.

Btw, você precisaria de uma inscrição Pluralsight para acessar este curso, que custa cerca de $29 mensais ou $299 anuais (14% de economia). Eu tenho um e também sugiro que todos os desenvolvedores tenham esse plano porque Pluralsight é como NetFlix para desenvolvedores de Software.
Tw tem mais de 5000+ cursos de boa qualidade sobre todos os tópicos mais recentes. Como nós programadores temos que aprender coisas novas todos os dias, um investimento de $299 USD não é mau.
Btw, ele também oferece um teste gratuito de 10 dias sem qualquer obrigação que permite que você assista a 200 horas de conteúdo. Você pode assistir a estes cursos gratuitamente assinando para aquele teste gratuito de 10 dias.

Java Programa para implementar o InOrder traversal de uma árvore binária

Aqui está a nossa solução completa para o algoritmo de inorder traversal em Java. Este programa usa um algoritmo recursivo para imprimir o valor de todos os nós de uma árvore binária usando o InOrder traversal.

Como eu já disse antes, durante a travessia de ordem o valor da sub-árvore esquerda é impresso primeiro, seguido pela raiz e sub-árvore direita. Se você estiver interessado no algoritmo iterativo, você pode verificar ainda mais este tutorial de implementação em ordem de travessia sem recursividade.
É tudo sobre como implementar inOrder traversal de uma árvore binária em Java usando recursividade. Você pode ver que o código é muito parecido com a travessia de preOrder com a única diferença na ordem que nós recursivamente chamamos o método. Neste caso, chamamos inOrder(node.left) primeiro e depois imprimimos o valor do nó.
Vale lembrar que em ordem de travessia é um algoritmo depth-first e imprime o nó de árvore em ordem ordenada se dada árvore binária for uma árvore de busca binária.
Na próxima parte deste artigo, vou compartilhar emOrder Traversal sem recorrência, enquanto isso, você pode tentar praticar seguindo a estrutura de dados e problemas de árvore binária.
Outras aprendizagens
Estruturas de dados e Algoritmos: Mergulho profundo usando Java
Algoritmos e Estruturas de Dados – Parte 1 e 2
Estruturas de Dados em Java 9 por Heinz Kabutz
Rasgando a Entrevista de Codificação – 189 Perguntas e Soluções
Grokking the Coding Interview: Patterns for Coding Questions
Outros tutoriais de estrutura de dados e algoritmos para programadores Java

• 10 Livros de Algoritmos Cada Programador Deve Ler (lista)
• Como implementar o algoritmo Quicksort em Java? (solução)
• 5 Livros para aprender estrutura de dados e algoritmos em Java? (livros)
• Top 50 Programas Java de Entrevistas de Codificação (ver aqui)
• 5 Cursos Gratuitos de Estrutura de Dados e Algoritmos para Programadores (cursos)
• Como verificar se uma String é um Palíndromo em Java?
• Como encontrar o número que falta em um array ordenado em Java?
• 10 Algoritmos Livros que Todo Programador Deve Ler (livros)
• 10 Cursos Gratuitos de Estrutura de Dados e Algoritmos para Programadores (cursos)
• 100+ Problemas de Codificação de Estrutura de Dados de Entrevistas (perguntas)
• Como imprimir a série Fibonacci em Java sem usar Recursion?
• Como verificar se um número inteiro é um poder de dois sem usar divisão ou operador de módulo?
• Como encontrar toda a permutação de String em Java?
• Primeiro 20 questões de entrevista de codificação de String (ver aqui)
• 50+ Problemas de Estrutura de Dados e Algoritmos de Entrevistas (questões)
• Como remover um elemento do array sem usar um terceiro…party library (veja aqui)
• Como encontrar o maior e menor número em um array em Java (veja aqui)
• Como encontrar dois números máximos em array inteiro em Java (veja aqui)