Planteamiento del Desafío

Dada una instancia de un árbol binario de búsqueda (BST), el objetivo principal es determinar todos los elementos que poseen la frecuencia de aparición más alta dentro de la estructura. Se considera que un valor es moda si ocurre tantas veces como cualquier otro valor.

Para resolver esto correctamente, se debe entender la definición operativa del BST bajo la cual:

• Todos los nodos pertenecientes al subárbol izquierdo tienen valores menores o iguales al nodo raíz.
• Todos los nodos pertenceientes al subárbol derecho tienen valores mayores o iguales al nodo raíz.
• Ambas subestructuras deben mantenerse válidas como árboles de búsqueda.

Ejemplo Estructura

Considere el siguiente caso donde el árbol contiene duplicados:

   1
    \
     2
    /
   2

La respuesta esperada para este caso particular sería el array [2].

Restricciones de Optimización

Una consideración clave en esta implementación es el consumo de memoria auxiliar. Aunque se puede utilizar un diccionario o mapa de hash para contar frecuencias, el desafío avanza buscando una solución que utilice espacio constante O(1), excluyendo la pila de recursión implícita utilizada durante el recorrido.

Lógica de la Solución

La característica fundamental de un BST es que una recurrencia inorden (In-Order Traversal) produce una secuencia ordenada. Al visitar los nodos en este orden específico, los valores repetidos aparecerán adyacentemente entre sí. Esto elimina la necesidad de un mapa de almacenamiento externo.

El algoritmo mantiene un estado interno que incluye:

• El valor del nodo previamente visitado.
• El contador actual de apariciones consecutivas.
• El contador máximo registrado hasta el momento.
• Una lista acumuladora para almacenar las modalidades encontradas.

Cuando se detecta un cambio en el valor del nodo, el contador local se reinicia a uno (indicando la primera aparición del nuevo número). Si el contador local iguala al máximo global, el número se agrega a la lista de resultados; si supera al máximo, la lista se limpia y se reemplaza con el nuevo valor ganador.

Implementación en JavaScript

A continuación se presenta una lógica refactorizada que sigue el patrón de recorrido inorden para cumplir con los requisitos de eficiencia:

/**
 * Definición básica del nodo del árbol
 */
function TreeNode(val, left, right) {
    this.val = val;
    this.left = left || null;
    this.right = right || null;
}

/**
 * Función principal para extraer las modas
 * @param {TreeNode} arbolRaiz
 * @returns {number[]}
 */
function encontrarModales(arbolRaiz) {
    if (!arbolRaiz) return [];

    // Estado del procesador de datos
    let valorPrecedente = null;
    let contadorConsecutivo = 0;
    let frecuenciaMaxima = 0;
    let resultadosFrecuentes = [];

    // Función auxiliar para recorrido recursivo
    const procesarNodo = (nodo) => {
        if (!nodo) return;

        // Visitar hijo izquierdo primero
        procesarNodo(nodo.left);

        // Lógica de conteo en tiempo real
        if (valorPrecedente !== null && nodo.val === valorPrecedente) {
            contadorConsecutivo += 1;
        } else {
            valorPrecedente = nodo.val;
            contadorConsecutivo = 1;
        }

        // Actualizar resultados según la frecuencia detectada
        if (contadorConsecutivo > frecuenciaMaxima) {
            frecuenciaMaxima = contadorConsecutivo;
            resultadosFrecuentes = [nodo.val];
        } else if (contadorConsecutivo === frecuenciaMaxima) {
            resultadosFrecuentes.push(nodo.val);
        }

        // Visitar hijo derecho
        procesarNodo(nodo.right);
    };

    procesarNodo(arbolRaiz);
    return resultadosFrecuentes;
}

Análisis de la Lógica

La función procesarNodo encapsula la recursión profunda. Es crucial notar cómo se maneja la transición de valores. En la primera iteración, el valorPrecedente es nulo, forzando el reinicio del contador a 1. A partir de ahí, comparaciones simples determinan si continuamos la secuencia actual o iniciamos una nueva.

La comparación contra frecuenciaMaxima dicta el destino del resultado. Si superamos el máximo histórico, descartamos lo acumulado anteriormente porque ya no es válido como máxima frecuencia. De igual manera, si encontramos múltiples valores con la misma frecuencia top, ambos se preservan en el array final.