Árboles binarios y recorridos

Una lista tiene un único siguiente. Un árbol puede abrir varios caminos. Para procesarlo no alcanza con avanzar: hay que decidir en qué orden visitar cada rama y qué hacer cuando el camino termina.

Un árbol es una definición recursiva

Un árbol binario está vacío o contiene una raíz y dos subárboles, izquierdo y derecho:

type BinaryNode<T> = {
  value: T;
  left: BinaryNode<T> | null;
  right: BinaryNode<T> | null;
};

Los nodos sin hijos son hojas. La profundidad cuenta enlaces desde la raíz hasta un nodo; la altura mide el camino más largo desde un nodo hasta una hoja. Estas medidas describen la forma del árbol, no la cantidad total de nodos.

Los tres recorridos en profundidad

Los recorridos en profundidad terminan una rama antes de pasar a otra. En preorden visitamos raíz, izquierda y derecha. En inorden hacemos izquierda, raíz y derecha. En postorden dejamos la raíz para el final: izquierda, derecha y raíz.

Las tres variantes recorren los mismos nodos. Lo único que cambia es el momento en que se procesa la raíz respecto de sus subárboles.

Inorden, escrito tal cual se define

Una implementación de inorden refleja directamente la definición:

const inOrder = <T>(node: BinaryNode<T> | null, values: T[]): void => {
  if (!node) return;
  inOrder(node.left, values);
  values.push(node.value);
  inOrder(node.right, values);
};

En un árbol binario de búsqueda, este recorrido produce las claves ordenadas. Preorden sirve para procesar padres antes que hijos; postorden, para liberar o calcular algo de los hijos antes de combinarlo en el padre.

Por niveles, con una cola

El recorrido en anchura, BFS, visita por niveles. Usa una cola: entra la raíz, sale el próximo nodo y entran sus hijos. Así se procesan primero todos los nodos de profundidad cero, luego los de profundidad uno y sucesivamente.

BFS es útil para encontrar la menor cantidad de enlaces hasta un objetivo o para imprimir una jerarquía nivel por nivel. DFS usa una pila explícita o la pila de llamadas; BFS necesita una cola.

Qué cuesta cada recorrido en memoria

Todo recorrido completo visita $n$ nodos y cuesta $O(n)$ tiempo. El espacio auxiliar de DFS es $O(h)$, donde $h$ es la altura: guarda el camino activo. BFS guarda la frontera y puede usar $O(w)$, donde $w$ es el ancho máximo.

En un árbol muy ancho, la cola domina la memoria. En uno degenerado, la profundidad puede llegar a $n$ y una versión recursiva puede desbordar la pila.

Para qué sirve cada recorrido

La regla para elegir es simple una vez que se ve: el recorrido se decide por cuándo hace falta el nodo respecto de sus hijos. Si el nodo se procesa antes, es previo; si hace falta que los hijos ya estén resueltos, es posterior; si el orden de las claves importa, es en orden.

Cierre

Un árbol binario se entiende como raíz más dos subárboles. Preorden, inorden y postorden cambian cuándo actúa la raíz; BFS cambia la estrategia completa y avanza por niveles. Elegí el recorrido según el orden que exige el resultado y la forma que puede tener el árbol.