El recorrido InOrder es una de las tres formas populares de recorrer una estructura de datos de árbol binario, siendo las otras dos el preOrder y el postOrder. Durante el algoritmo de recorrido en orden, se explora primero el subárbol de la izquierda, seguido de la raíz, y finalmente los nodos del subárbol de la derecha. Se comienza el recorrido desde la raíz, luego se va al nodo de la izquierda, luego se vuelve a ir al nodo de la izquierda hasta llegar a un nodo hoja. En ese momento, se imprime el valor del nodo o se marca como visitado y se pasa al subárbol de la derecha. Se continúa con el mismo algoritmo hasta visitar todos los nodos del árbol binario. El InOrder traversal también se conoce como el algoritmo left-node-right o left-root-right traversal o LNR traversal.
Similar al algoritmo preOrder, también es un algoritmo depth-first porque explora la profundidad de un árbol binario antes de explorar los hermanos. Dado que es uno de los algoritmos de árbol binario fundamentales, es bastante popular en las entrevistas de programación.
Estos algoritmos de recorrido son también la base para aprender algoritmos de árbol binario más avanzados, por lo que todo programador debería aprender, entender y saber cómo implementar el algoritmo inOrder y otros algoritmos de recorrido.
La forma más sencilla de implementar el algoritmo de recorrido inOrder en Java o en cualquier lenguaje de programación es utilizando la recursión. Dado que el árbol binario es una estructura de datos recursiva, la recursión es la opción natural para resolver un problema basado en el árbol. El método inOrder() de la clase BinaryTree implementa la lógica para recorrer un árbol binario utilizando la recursión.
Desde el punto de vista de la Entrevista, el recorrido InOrder es extremadamente importante porque también imprime los nodos de un árbol de búsqueda binario en el orden ordenado pero sólo si el árbol dado es un árbol de búsqueda binario. Si recuerdas, en el BST, el valor de los nodos del subárbol de la izquierda es inferior al de la raíz, y los valores de los nodos del subárbol de la derecha son superiores al de la raíz. La travesía en orden significa literalmente EN orden, es decir, las notas se imprimen en el orden o ordenadas.
Por cierto, aunque estos tres algoritmos (pre-orden, en-orden y post-orden) son algoritmos populares de travesía del árbol binario, pero no son los únicos. También tienes otras formas de recorrer un árbol binario, por ejemplo, el recorrido por niveles (Ver Estructura de Datos y Algoritmos: Profundización).

El algoritmo recursivo para implementar el recorrido InOrder de un árbol binario

El algoritmo recursivo de recorrido inorder es muy simple. Sólo hay que llamar al método inOrder() de la clase BinaryTree en el orden en que se quiere visitar el árbol. Lo más importante es incluir el caso base, que es la clave de cualquier algoritmo recursivo.
Por ejemplo, en este problema, el caso base es que llegas al nodo hoja y no hay más nodo que explorar, en ese momento la recursión empieza a decaer. Aquí están los pasos exactos para recorrer el árbol binario utilizando InOrder traversal:

1. visitar el nodo izquierdo
2. imprimir el valor de la raíz
3. visitar el nodo derecho

y aquí está el código de ejemplo para implementar este algoritmo utilizando la recursión en Java:
De forma similar al método preOrder() del último ejemplo, existe otro método inOrder() que expone al público el recorrido InOrder y llama a este método privado que realmente realiza el recorrido InOrder.
Esta es la forma estándar de escribir un método recursivo que toma una entrada, hace que sea más fácil para un cliente llamar al método.

public void inOrder() { inOrder(root);}

Puedes ver que empezamos con root y luego llamamos recursivamente al método inOrder() con node.left, lo que significa que estamos bajando en el subárbol de la izquierda hasta que llegamos a node == null, lo que significa que el último nodo era un nodo hoja.
En este momento, el método inOrder() regresará y ejecutará la siguiente línea, que imprime el node.data. Después de que su recursiva inOrder() llamada con node.right, que se iniciará el mismo proceso again.
También puede comprobar la estructura de datos y algoritmos Parte 1 y 2 cursos en Pluralsight para aprender más acerca de los algoritmos y cómo diseñar sus propios algoritmos.

Btw, usted necesitaría una membresía Pluralsight para acceder a este curso, que cuesta alrededor de $ 29 mensuales o $ 299 anuales (14% de ahorro). Yo tengo uno y también sugiero que todos los desarrolladores tengan ese plan porque Pluralsight es como NetFlix para los desarrolladores de Software.
Tiene más de 5000+ cursos de buena calidad sobre todos los temas más recientes. Como los programadores tenemos que aprender cosas nuevas todos los días, una inversión de 299 USD no está mal.
Además, también ofrece una prueba gratuita de 10 días sin ningún compromiso que te permite ver 200 horas de contenido. Usted puede ver estos cursos de forma gratuita mediante la firma de esa prueba gratuita de 10 días.

Programa de Java para implementar InOrder traversal de un árbol binario

Aquí está nuestra solución completa al algoritmo inorder traversal en Java. Este programa utiliza un algoritmo recursivo para imprimir el valor de todos los nodos de un árbol binario utilizando InOrder traversal.
Como te he dicho antes, durante el in-order traversal se imprime primero el valor del subárbol de la izquierda, seguido del de la raíz y el de la derecha. Si estás interesado en el algoritmo iterativo, puedes consultar este tutorial de implementación del recorrido en orden sin recursión.
Eso es todo sobre cómo implementar el recorrido en orden de un árbol binario en Java usando recursión. Puedes ver que el código es bastante similar al traversal inOrder con la única diferencia en el orden en que llamamos recursivamente al método. En este caso, llamamos primero a inOrder(node.left) y luego imprimimos el valor del nodo.
Vale la pena recordar que el traversal in order es un algoritmo depth-first e imprime el nodo del árbol en ordenado si el árbol binario dado es un árbol de búsqueda binaria.
En la siguiente parte de este artículo, compartiré inOrder traversal sin recursión, mientras tanto, puedes intentar practicar los siguientes problemas de estructuras de datos y árboles binarios.
Aprendizaje adicional
Estructuras de datos y algoritmos: Deep Dive Using Java
Algorithms and Data Structures – Part 1 and 2
Data Structures in Java 9 by Heinz Kabutz
Cracking the Coding Interview – 189 Questions and Solutions
Grokking the Coding Interview: Patrones para preguntas de codificación
Otros tutoriales de estructuras de datos y algoritmos para programadores de Java

• 10 libros de algoritmos que todo programador debería leer (lista)
• ¿Cómo implementar el algoritmo Quicksort en Java? (solución)
• 5 Libros para aprender estructura de datos y algoritmos en Java? (libros)
• Los 50 mejores programas Java de Entrevistas de Codificación (ver aquí)
• 5 cursos gratuitos de estructura de datos y algoritmos para programadores (cursos)
• ¿Cómo comprobar si una cadena es un palíndromo en Java?
• ¿Cómo encontrar el número que falta en un array ordenado en Java?
• 10 libros de algoritmos que todo programador debería leer (libros)
• 10 cursos gratuitos de estructura de datos y algoritmos para programadores (cursos)
• 100+ problemas de codificación de estructura de datos de entrevistas (preguntas)
• ¿Cómo imprimir la serie de Fibonacci en Java sin usar recursión?
• ¿Cómo comprobar si un entero es una potencia de dos sin utilizar el operador de división o módulo?
• ¿Cómo encontrar todas las permutaciones de String en Java?
• Las 20 mejores preguntas de la entrevista de codificación de cadenas (ver aquí)
• 50+ Problemas de estructura de datos y algoritmos de las entrevistas (preguntas)
• ¿Cómo eliminar un elemento de la matriz sin usar una biblioteca de terceros?party library (check here)
• Cómo encontrar el mayor y el menor número en un array en Java (leer aquí)
• Cómo encontrar dos números máximos en un array de enteros en Java (comprobar aquí)