Recorridos de árboles: inorden, preorden y postorden explicados

Un árbol almacena datos, pero su valor emerge cuando lo recorres: visitas cada nodo en un orden determinado y aplicas una operación (imprimir, evaluar, copiar, serializar). La elección del orden no es trivial: el mismo árbol produce resultados muy distintos según cómo lo visites, y cada orden tiene su caso de uso.

En este artículo nos concentramos en los tres recorridos clásicos en profundidad (DFS) sobre árboles: inorden, preorden y postorden. El cuarto recorrido, por niveles (BFS), usa una cola y lo vemos en el siguiente artículo.

Este es el tercer artículo de Cómo se busca y se recorre.

La idea central

Un árbol binario tiene para cada nodo tres componentes: el nodo en sí, su subárbol izquierdo y su subárbol derecho. Los tres recorridos en profundidad se distinguen en el orden en que visitan esos tres componentes:

• Preorden: raíz → izquierda → derecha

• Inorden: izquierda → raíz → derecha

• Postorden: izquierda → derecha → raíz

Todos son naturalmente recursivos: la definición misma es recursiva.

Ejemplo de referencia

Usaremos este árbol binario de búsqueda para ilustrar cada recorrido:

           8
         /   \
        3     10
       / \      \
      1   6      14
         / \    /
        4   7  13

Preorden (raíz → izquierda → derecha)

void preorden(Nodo n) {
    if (n == null) return;
    visitar(n);             // 1. raíz
    preorden(n.izq);        // 2. izquierda
    preorden(n.der);        // 3. derecha
}

Sobre el árbol de ejemplo, produce:

8, 3, 1, 6, 4, 7, 10, 14, 13

¿Para qué sirve?

• Copiar o serializar un árbol: al procesar primero el nodo, puedes reconstruir el árbol si guardas también marcadores para null. El recorrido en preorden es la base de la serialización tipo "dump".

• Evaluar expresiones en notación prefija: (+ 3 4) en lisp es preorden.

• Navegar un árbol de directorios mostrando cada carpeta antes de entrar en ella.

Inorden (izquierda → raíz → derecha)

void inorden(Nodo n) {
    if (n == null) return;
    inorden(n.izq);         // 1. izquierda
    visitar(n);             // 2. raíz
    inorden(n.der);         // 3. derecha
}

Sobre el árbol de ejemplo:

1, 3, 4, 6, 7, 8, 10, 13, 14

Los valores salen en orden creciente. Esto solo pasa en un BST, pero es una propiedad tremendamente útil.

¿Para qué sirve?

• Obtener los elementos de un BST ordenados sin necesidad de sort explícito.

• Validar que un árbol binario es un BST: si recorrerlo inorden produce una secuencia ordenada, es BST.

• Evaluar expresiones en notación infija (parsear expresiones matemáticas con paréntesis).

Postorden (izquierda → derecha → raíz)

void postorden(Nodo n) {
    if (n == null) return;
    postorden(n.izq);       // 1. izquierda
    postorden(n.der);       // 2. derecha
    visitar(n);             // 3. raíz
}

Sobre el árbol de ejemplo:

1, 4, 7, 6, 3, 13, 14, 10, 8

¿Para qué sirve?

• Liberar memoria: si procesas los hijos antes que el padre, nunca dejas punteros colgando. Esta es la razón por la cual los destructores que recorren estructuras suelen usar postorden.

• Evaluar expresiones en notación postfija (RPN): 3 4 + es postorden. Las calculadoras HP y el lenguaje Forth trabajan así.

• Calcular tamaños, sumas o propiedades agregadas: para saber el tamaño del subárbol en un nodo, primero debes saber los tamaños de sus hijos.

• Build systems y schedulers: el nodo solo se puede procesar cuando sus dependencias (hijos) ya lo fueron.

Un ejemplo útil: calcular la altura

El cálculo de altura es postorden natural: necesitas las alturas de los hijos antes de calcular la del padre.

int altura(Nodo n) {
    if (n == null) return -1;
    int alturaIzq = altura(n.izq);
    int alturaDer = altura(n.der);
    return 1 + Math.max(alturaIzq, alturaDer);
}

Esto no es "visitar y luego recorrer"; es recorrer los hijos, obtener sus alturas y usar el resultado para el padre. Clásico postorden.

Implementación en PHP

class Nodo {
    public mixed $valor;
    public ?Nodo $izq = null;
    public ?Nodo $der = null;
    public function __construct(mixed $valor) {
        $this->valor = $valor;
    }
}

function preorden(?Nodo $n): void {
    if ($n === null) return;
    echo $n->valor . " ";
    preorden($n->izq);
    preorden($n->der);
}

function inorden(?Nodo $n): void {
    if ($n === null) return;
    inorden($n->izq);
    echo $n->valor . " ";
    inorden($n->der);
}

function postorden(?Nodo $n): void {
    if ($n === null) return;
    postorden($n->izq);
    postorden($n->der);
    echo $n->valor . " ";
}

Versión iterativa con pila

Recursión es lo más natural, pero si tu árbol es muy profundo puedes saturar el call stack. Las versiones iterativas usan una pila explícita.

Preorden iterativo

void preordenIter(Nodo raiz) {
    if (raiz == null) return;
    Deque<Nodo> pila = new ArrayDeque<>();
    pila.push(raiz);
    while (!pila.isEmpty()) {
        Nodo n = pila.pop();
        visitar(n);
        if (n.der != null) pila.push(n.der);
        if (n.izq != null) pila.push(n.izq); // izq último para procesarlo primero
    }
}

Inorden iterativo

void inordenIter(Nodo raiz) {
    Deque<Nodo> pila = new ArrayDeque<>();
    Nodo actual = raiz;
    while (actual != null || !pila.isEmpty()) {
        while (actual != null) {
            pila.push(actual);
            actual = actual.izq;
        }
        actual = pila.pop();
        visitar(actual);
        actual = actual.der;
    }
}

Postorden iterativo

La versión iterativa de postorden es la más incómoda. Un truco: ejecuta preorden "inverso" (raíz → der → izq) y al final invierte la salida.

void postordenIter(Nodo raiz) {
    if (raiz == null) return;
    Deque<Nodo> pila = new ArrayDeque<>();
    Deque<Nodo> salida = new ArrayDeque<>();
    pila.push(raiz);
    while (!pila.isEmpty()) {
        Nodo n = pila.pop();
        salida.push(n);
        if (n.izq != null) pila.push(n.izq);
        if (n.der != null) pila.push(n.der);
    }
    while (!salida.isEmpty()) visitar(salida.pop());
}

Cómo elegir el recorrido correcto

Pregúntate:

1. ¿Necesito procesar el padre antes que los hijos? Preorden.

2. ¿Necesito procesar el padre entre los hijos? Inorden.

3. ¿Necesito procesar los hijos antes que el padre? Postorden.

Algunas reglas prácticas:

• Obtener datos ordenados de un BST → inorden.

• Serializar/deserializar manteniendo estructura → preorden.

• Calcular agregados (altura, tamaño, suma, máximo) → postorden.

• Liberar memoria o ejecutar "dependencias primero" → postorden.

• Evaluar expresiones → depende de la notación (prefija / infija / postfija).

Ejemplo: validar si un árbol es un BST

Una manera elegante es usar inorden y verificar que cada nuevo valor sea mayor que el anterior:

Nodo anterior = null;
boolean esBST = true;

void validar(Nodo n) {
    if (n == null || !esBST) return;
    validar(n.izq);
    if (anterior != null && n.valor <= anterior.valor) esBST = false;
    anterior = n;
    validar(n.der);
}

Una sola pasada O(n).

Complejidad

RecorridoTiempoEspacioPre/In/Postorden (recursivo)O(n)O(h) en stack, donde h es la alturaPre/In/Postorden (iterativo)O(n)O(h) en pila explícita

Para árboles balanceados h = log n; para árboles desbalanceados puede ser h = n (caso peor).

Ventajas y desventajas

Ventajas:

• Cada recorrido se escribe en 3-4 líneas en versión recursiva.

• Cubren la mayoría de necesidades sobre árboles.

• Complejidad O(n) para visitar todo.

Desventajas:

• Recursión profunda puede saturar stack en árboles desbalanceados grandes.

• Iterativo con postorden es poco intuitivo.

• En árboles muy anchos y poco profundos, BFS es más natural que DFS.

Casos de uso reales

1. Renderizar el DOM: preorden.

2. Serializar a JSON/XML: preorden.

3. Liberar memoria: postorden.

4. Evaluar ASTs de compiladores: postorden.

5. Obtener entradas ordenadas de un TreeMap: inorden (por debajo).

6. Validar y recorrer expresiones matemáticas: variable según notación.

7. Calcular métricas sobre estructuras jerárquicas (tamaño de directorios, tiempo total): postorden.

Errores comunes

1. Confundir el orden de recorrido con el resultado deseado

"Recorrer inorden" no siempre produce ordenado; solo lo hace en un BST. Fuera de BST, inorden produce una secuencia sin significado particular.

2. Olvidar el caso base null

Cada función recursiva debe verificar if (n == null) return;. Olvidarlo lanza NPE.

3. Modificar el árbol durante el recorrido

Insertar o eliminar nodos mientras recorres puede crear bucles infinitos o saltarte nodos. Acumula los cambios y aplícalos después.

4. Asumir que la recursión es "gratis"

En árboles desbalanceados profundos, recursión puede desbordar el stack. Si tus árboles no están balanceados y son grandes, usa la versión iterativa.

5. Confundir preorden con postorden en serialización

Si serializas preorden y deserializas postorden, obtienes basura. Sé consistente.

6. Ignorar que inorden/preorden/postorden, solos, no identifican un árbol

Dos árboles distintos pueden tener el mismo inorden. Para reconstruir un árbol binario único necesitas dos recorridos (inorden + preorden, o inorden + postorden). Este es un problema clásico de entrevistas.

Resumen

Inorden, preorden y postorden son los tres recorridos en profundidad clásicos de un árbol binario. Difieren en cuándo se procesa el nodo respecto a sus hijos: antes (preorden), entre (inorden) o después (postorden). Inorden en un BST produce valores ordenados; preorden es ideal para serializar; postorden, para liberar memoria y calcular agregados.

Todos son O(n) en tiempo y O(h) en memoria. La versión recursiva es directa; la iterativa con pila explícita es útil para árboles muy profundos.

En el siguiente artículo cambiamos a recorrido por niveles: BFS, que usa una cola en lugar de una pila y es la base de algoritmos como grados de separación o camino más corto en grafos sin peso.