Descripción del problema

El recorrido por niveles (Level Order Traversal) consiste en visitar cada nodo de un árbol binario de forma horizontal, procesando todos los nodos de un nivel antes de pasar al siguiente, generalmente de izquierda a derecha.

Dado un árbol binario, el objetivo es devolver una estructura de datos que agrupe los valores de los nodos por cada nivel.

Ejemplo:

Para un árbol con la estructura {3, 9, 20, #, #, 15, 7}, el resultado esperado sería:

[
  [3],
  [9, 20],
  [15, 7]
]

Estrategia de resolución: Uso de Colas

Para implementar este algoritmo de manera eficiente, se utiliza una cola (Queue), que sigue el principio FIFO (First-In, First-Out). Esta estructura permite gestionar el orden de visita de los nodos nivel por nivel.

El proceso se divide en los siguientes pasos:

1. Inicialización: Se crea una cola y se inserta el nodo raíz. Si el árbol está vacío, se retorna una lista vacía.
2. Iteración por niveles: Mientras la cola no esté vacía, se determina el número de elementos que contiane en ese instante (esto representa la cantidad de nodos en el nivel actual).
3. Procesamiento de nodos: Se extraen exactamente esos nodos de la cola uno por uno:
   • Se añade su valor a una lista temporal del nivel.
   • Si el nodo tiene hijos (izquierdo o derecho), se insertan en la cola para ser procesados en la siguiente iteración.
4. Almacenamiento: Una vez finalizado el nivel, la lista temopral se añade al resultado final.

Implementación técnica en Go

A continuación se presenta una implementación optimizada utilizando el lenguaje Go. Se hace énfasis en la gestión de memoria mediante el uso de slices con capacidad predefinida cuando es posible.

type NodoArbol struct {
    Valor int
    Izquierdo *NodoArbol
    Derecho   *NodoArbol
}

/**
 * Función para realizar el recorrido por niveles.
 * @param raiz Puntero al nodo raíz del árbol.
 * @return Una matriz de enteros organizada por niveles.
 */
func obtenerRecorridoNiveles(raiz *NodoArbol) [][]int {
    var resultado [][]int
    
    // Validación inicial de árbol vacío
    if raiz == nil {
        return resultado
    }

    // Inicialización de la cola con el nodo raíz
    colaProcesamiento := []*NodoArbol{raiz}

    for len(colaProcesamiento) > 0 {
        // Cantidad de nodos en el nivel actual
        nodosEnNivel := len(colaProcesamiento)
        valoresDelNivel := make([]int, 0, nodosEnNivel)

        for i := 0; i < nodosEnNivel; i++ {
            // Extracción del primer elemento de la cola
            nodoActual := colaProcesamiento[0]
            colaProcesamiento = colaProcesamiento[1:]

            // Registro del valor del nodo
            valoresDelNivel = append(valoresDelNivel, nodoActual.Valor)

            // Inserción de hijos en la cola para el próximo nivel
            if nodoActual.Izquierdo != nil {
                colaProcesamiento = append(colaProcesamiento, nodoActual.Izquierdo)
            }
            if nodoActual.Derecho != nil {
                colaProcesamiento = append(colaProcesamiento, nodoActual.Derecho)
            }
        }
        
        // Se agrega el nivel procesado al conjunto final
        resultado = append(resultado, valoresDelNivel)
    }

    return resultado
}

Análisis de complejidad

• Complejidad Temporal: O(N), donde N es el número total de nodos en el árbol, ya que cada nodo se visita exactamente una vez.
• Complejidad Espacial: O(W), donde W es el ancho máximo del árboll (el número máximo de nodos en un solo nivel), debido al almacenamiento en la cola.