Problema

Dado un árbol de búsqueda binaria (BST), encontrar el k-ésimo valor más pequeño. Por ejemplo, en el siguiente árbol, el tercer valor más pequeño es 4.

Conceptos básicos

Árbol binario:

• Estructura jerárquica donde cada nodo tiene máximo dos hijos
• Definición de nodo:

interface NodoArbol {
  valor: number;
  izquierdo?: NodoArbol | null;
  derecho?: NodoArbol | null;
}

Ejemplo de estructura:

const arbol: NodoArbol = {
  valor: 5,
  izquierdo: {
    valor: 3,
    izquierdo: { valor: 2, izquierdo: null, derecho: null },
    derecho: { valor: 4, izquierdo: null, derecho: null }
  },
  derecho: {
    valor: 7,
    izquierdo: { valor: 6, izquierdo: null, derecho: null },
    derecho: { valor: 8, izquierdo: null, derecho: null }
  }
};

Recorridos de árboles

Recorrido en orden (Inorden):

• Visita subárbol izquierdo, luego raíz, luego subárbol derecho
• Produce valores ordenados en BST

function recorrerEnOrden(nodo: NodoArbol | null): number[] {
  const resultados: number[] = [];
  if (!nodo) return resultados;
  
  resultados.push(...recorrerEnOrden(nodo.izquierdo));
  resultados.push(nodo.valor);
  resultados.push(...recorrerEnOrden(nodo.derecho));
  
  return resultados;
}

Árbol de búsqueda binaria (BST):

• Para cualquier nodo, los valores del subárbol izquierdo ≤ valor del nodo
• Los valores del subárbol derecho ≥ valor del nodo
• Permite búsquedas eficientes mediante división binaria

Solución

Enfoque: Aprovechar el recorrido en orden para obtener valores ordenados y seleccionar el k-ésimo elemento.

Implementación optimizada:

function encontrarKesimo(nodoRaiz: NodoArbol | null, k: number): number | null {
  const pila: NodoArbol[] = [];
  let actual: NodoArbol | null = nodoRaiz;
  let contador = 0;

  while (pila.length > 0 || actual) {
    while (actual) {
      pila.push(actual);
      actual = actual.izquierdo;
    }
    
    actual = pila.pop()!;
    contador++;
    
    if (contador === k) return actual.valor;
    
    actual = actual.derecho;
  }
  
  return null;
}

Pruebas

describe('Búsqueda del k-ésimo valor más pequeño', () => {
  const arbol: NodoArbol = { /* Estructura definida anteriormente */ };

  test('Caso estándar', () => {
    expect(encontrarKesimo(arbol, 3)).toBe(4);
  });

  test('k fuera de rango', () => {
    expect(encontrarKesimo(arbol, 0)).toBeNull();
    expect(encontrarKesimo(arbol, 100)).toBeNull();
  });
});