Recorrido Inorden en Árboles Binarios

El recorrido inorden es un patrón de visita para árboles binarios donde cada nodo se procesa siguiendo el orden: subárbol izqiuerdo, nodo actual y subárbol derecho. Esta secuencia se aplica de manera recursiva a todas las ramas del árbol.

Implementación Iterativa

Para ejecutar el recorrido inorden sin recursión explícita, se emplea una pila para emular la pila de llamadas. El algoritmo inicia desde la raíz y itera: mientras exista un nodo actual o la pila no esté vacía, se apilan todos los nodos izquierdos accesibles. Posteriormente, se extrae un nodo de la pila, se visita, y se continúa con su subárbol derecho.

Ejemplo de Código en Python

def inorder_iterative(root):
    traversal_result = []
    node_stack = []
    current_node = root
    while current_node or node_stack:
        while current_node:
            node_stack.append(current_node)
            current_node = current_node.left
        current_node = node_stack.pop()
        traversal_result.append(current_node.val)
        current_node = current_node.right
    return traversal_result

Enfoque Recursivo

La versión recursiva sigue directamente la definición: primero se recorre el subárbol izquierdo, luego se accede al nodo raíz y finalmente se recorre el subárbol derecho. La condición de terminación se alcanza cuando el nodo es nulo.

Código Recursivo

def inorder_recursive(root):
    if root is None:
        return []
    left_part = inorder_recursive(root.left)
    current_value = [root.val]
    right_part = inorder_recursive(root.right)
    return left_part + current_value + right_part

Árbol de Ejemplo y Verificación

Se construye un árbol con raíz en 5, hijo derecho en 8, y el hijo izquierdo de 8 es 6. El recorrido inorden produce la secuencia [5, 6, 8].

Construcción del Árbol

class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

tree_root = TreeNode(5)
tree_root.right = TreeNode(8)
tree_root.right.left = TreeNode(6)

Prueba de Funcionalidad

print(inorder_recursive(tree_root))  # Resultado: [5, 6, 8]
print(inorder_iterative(tree_root))  # Resultado: [5, 6, 8]

Aplicaciones Prácticas

El recorrido inorden es esencial en árboles de búsqueda binaria (BST), ya que dveuelve los valores en orden ascendente. Esto habilita funcionalidades como:

• Validar la propiedad BST comprobando que la secuencia sea monotónicamente creciente.
• Extraer una lista ordenada de elemenots sin ordenamiento adicional.
• Localizar el k-ésimo elemento menor recorriendo hasta el k-ésimo nodo visitado.