Recorrido de árboles binarios: preorden, inorden, postorden y por niveles

Por qué importa el orden del recorrido

Un árbol no tiene un único orden natural, así que cada algoritmo elige el que encaja con su tarea. El recorrido inorden de un árbol binario de búsqueda produce las claves en orden. El preorden visita al padre antes que a sus hijos, que es lo que necesitas para copiar un árbol o escribirlo de modo que se pueda reconstruir. El postorden visita a los hijos antes que al padre, que es lo que necesitas para borrar un árbol, calcular tamaños de carpetas o evaluar un árbol de expresiones. El orden por niveles encuentra primero el nodo menos profundo e imprime el árbol fila por fila.

Los cuatro órdenes en un ejemplo

Usamos este árbol: raíz 1 con hijos 2 y 3; el nodo 2 tiene hijos 4 y 5; el nodo 3 tiene un hijo derecho 6.

        1
       / \
      2   3
     / \   \
    4   5   6

Una forma sencilla de recordar los tres primeros: el nombre dice dónde va el nodo. Pre significa antes de ambos subárboles, in entre ellos y post después de ellos. El subárbol izquierdo siempre se visita antes que el derecho.

Implementaciones recursivas

Las versiones recursivas reflejan directamente las definiciones. Cada función visita el nodo en una línea distinta.

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right
def preorder(node, out):
    if node:
        out.append(node.val)
        preorder(node.left, out)
        preorder(node.right, out)
    return out
def inorder(node, out):
    if node:
        inorder(node.left, out)
        out.append(node.val)
        inorder(node.right, out)
    return out
def postorder(node, out):
    if node:
        postorder(node.left, out)
        postorder(node.right, out)
        out.append(node.val)
    return out
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))
print(preorder(root, []))   # [1, 2, 4, 5, 3, 6]
print(inorder(root, []))    # [4, 2, 5, 1, 3, 6]
print(postorder(root, []))  # [4, 5, 2, 6, 3, 1]

Preorden e inorden iterativos con una pila

La recursión usa la pila de llamadas. Para evitar los límites de recursión en árboles profundos, gestiona tú la pila. En preorden, saca un nodo, visítalo y apila el hijo derecho antes que el izquierdo para que el izquierdo se procese primero.

En inorden, baja por la izquierda tanto como puedas, apilando nodos por el camino. Cuando ya no puedas ir más a la izquierda, saca un nodo, visítalo y pasa a su hijo derecho.

def preorder_iter(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out
def inorder_iter(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:              # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out
print(preorder_iter(root))  # [1, 2, 4, 5, 3, 6]
print(inorder_iter(root))   # [4, 2, 5, 1, 3, 6]

Postorden iterativo y orden por niveles

El postorden iterativo es el más delicado. Un enfoque limpio usa una marca: apila cada nodo dos veces, la segunda marcado como listo para visitarse después de sus hijos. El orden por niveles usa una cola en lugar de una pila; procesar la cola nivel por nivel también te da la profundidad de cada nodo.

from collections import deque
def postorder_iter(root):
    out, stack = [], [(root, False)] if root else []
    while stack:
        node, children_done = stack.pop()
        if children_done:
            out.append(node.val)
        else:
            stack.append((node, True))
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
    return out
def level_order(root):
    levels, queue = [], deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):   # nodes of the current level
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels
print(postorder_iter(root))  # [4, 5, 2, 6, 3, 1]
print(level_order(root))     # [[1], [2, 3], [4, 5, 6]]

Otro truco común para el postorden: ejecuta un preorden modificado (nodo, derecha, izquierda) e invierte el resultado.

Complejidad temporal y espacial

Aquí n es el número de nodos, h la altura y w el ancho máximo. En un árbol balanceado h es aproximadamente log2(n) y w puede ser cercano a n/2; en un árbol en forma de cadena h es n y w es 1.

Errores comunes

• Apilar el hijo izquierdo antes que el derecho en el preorden iterativo. Una pila es LIFO, así que el hijo que quieres primero debe apilarse el último.
• Olvidar el árbol vacío: toda función debe devolver un resultado vacío cuando root is None.
• Usar una list con pop(0) como cola en el orden por niveles. Cuesta O(n) por extracción; usa collections.deque.
• Depender de la recursión en árboles muy profundos. Python se detiene en su límite de recursión (unos 1000 por defecto) con RecursionError.
• Esperar que un solo recorrido identifique un árbol. El preorden por sí solo es ambiguo; preorden más inorden (con valores distintos) basta para reconstruirlo.

Cuándo usar cada recorrido

Preorden, inorden y postorden son formas de búsqueda en profundidad; el orden por niveles es la búsqueda en anchura aplicada a un árbol. Las mismas ideas se extienden a grafos generales, donde además necesitas un conjunto de nodos visitados.