Recorrer un árbol nivel por nivel suena complicado hasta que entiendes la lógica detrás de BFS (Breadth First Search). Aprenderás a implementar este algoritmo en Python usando colas, contar niveles del árbol y guardar el orden de visita, una habilidad clave para entrevistas técnicas y problemas de grafos.

¿Qué es BFS y por qué se implementa con colas?

BFS recorre un árbol o grafo nivel por nivel, visitando primero todos los nodos cercanos a la raíz antes de bajar al siguiente nivel. La estructura natural para lograrlo es una cola, porque respeta el orden FIFO: lo primero que entra es lo primero que sale.

¿Cuál es la diferencia entre BFS y DFS? BFS usa colas y recorre por niveles. DFS usa pilas y baja en profundidad antes de explorar hermanos. Ambos visitan todos los nodos, pero en orden distinto.

La función parte de un nodo raíz, aunque en otros problemas podrías recibir coordenadas de una cuadrícula o cualquier estructura que represente conexiones.

¿Cómo se construye la función BFS desde cero?

La idea es devolver una lista con los nodos en el orden en que los visitas. Si la raíz es nula, retornas una lista vacía sin más cálculos.

La estructura básica de la función incluye:

• Una lista respuesta para guardar los nodos visitados en orden.
• Una cola inicializada con la raíz como primer elemento.
• Una variable nivel que arranca en cero y crece con cada capa procesada.
• Un ciclo while que itera mientras la cola tenga elementos.

python def bfs(raiz): if not raiz: return [] respuesta = [raiz] cola = [raiz] nivel = 0 while cola: for _ in range(len(cola)): nodo_actual = cola.pop(0) for hija in nodo_actual.hijas: cola.append(hija) respuesta.append(hija) nivel += 1 print(f"La cantidad de niveles de este árbol es {nivel}") return respuesta

El detalle fino está en la línea del for _ in range(len(cola)): capturas cuántos nodos hay en el nivel actual antes de empezar a sacarlos. Así, aunque la cola crezca al añadir hijos, solo procesas los del nivel que te interesa.

¿Cómo se cuentan los niveles del árbol con BFS?

Cada vez que terminas de procesar todos los nodos del nivel actual, sumas uno a la variable nivel. Como el ciclo interno solo recorre los elementos que había al inicio de esa iteración, el conteo refleja exactamente la profundidad del árbol.

¿Por qué uso un guion bajo en el for? Porque no necesitas el índice, solo quieres iterar tantas veces como nodos haya en ese nivel. El underscore es la convención en Python para variables que no usarás.

¿Cómo adapto BFS para árboles binarios o n-arios?

El ejemplo anterior asume un árbol n-ario, donde cada nodo tiene un atributo hijas que es una lista. Por eso iteras con for hija in nodo_actual.hijas.

Si trabajas con un árbol binario clásico, donde cada nodo tiene izquierda y derecha, cambias el bucle interno por dos verificaciones simples:

• Si nodo_actual.izquierda existe, haces cola.append(nodo_actual.izquierda).
• Si nodo_actual.derecha existe, haces cola.append(nodo_actual.derecha).

La lógica de la cola, los niveles y la respuesta se mantiene idéntica. Solo cambia cómo accedes a los hijos.

¿Cómo imprimo el árbol mientras lo recorro?

Dentro del ciclo, después de extraer nodo_actual con cola.pop(0), puedes imprimir su valor con print(nodo_actual.valor). Eso te da en consola el recorrido completo en orden BFS, útil para depurar y verificar que tu implementación funciona.

¿Cuándo termina el ciclo while?

El while cola sigue iterando hasta que la cola quede vacía. Esto ocurre cuando llegas al último nivel del árbol, donde los nodos ya no tienen hijos que agregar. En cada vuelta sacas los actuales y metes a los siguientes; cuando no hay siguientes, la cola se vacía y el ciclo termina de forma natural.

Esa es la elegancia de BFS con colas: no necesitas saber cuántos niveles tiene el árbol de antemano, la propia estructura te lleva hasta el final.

¿Qué problema resolverías tú con BFS? Comparte en los comentarios cómo aplicarías esta lógica en una cuadrícula o en un grafo de conexiones.