Árboles Binarios

Un árbol binario es una estructura jerárquica donde cada nodo tiene máximo dos hijos (izquierdo y derecho). Los Binary Search Trees (BST) tienen una propiedad adicional: todos los nodos del subárbol izquierdo son menores, y los del derecho son mayores.

Esto hace búsqueda, inserción y eliminación O(log n) en un árbol balanceado, igual que la búsqueda binaria en un array pero en una estructura dinámica que puede crecer y encogerse eficientemente.

DFS (Depth-First Search) explora tan profundo como puede antes de retroceder. Tiene tres variantes según cuándo visitas el nodo raíz: preorden (raíz, izquierda, derecha), inorden (izquierda, raíz, derecha) y postorden (izquierda, derecha, raíz). El inorden de un BST produce los elementos en orden ascendente. BFS (Breadth-First Search) visita nivel por nivel usando una Queue.

BFS encuentra el camino más corto y es ideal para "nivel más profundo de un nodo" o "árbol de decisión por niveles".

class NodoArbol {
  constructor(val) {
    this.val = val;
    this.izq = null;
    this.der = null;
  }
}

// Recorridos DFS
function inorder(nodo) { // izq, raíz, der
  if (!nodo) return [];
  return [...inorder(nodo.izq), nodo.val, ...inorder(nodo.der)];
}

function preorder(nodo) { // raíz, izq, der
  if (!nodo) return [];
  return [nodo.val, ...preorder(nodo.izq), ...preorder(nodo.der)];
}

function postorder(nodo) { // izq, der, raíz
  if (!nodo) return [];
  return [...postorder(nodo.izq), ...postorder(nodo.der), nodo.val];
}

// BFS (nivel por nivel)
function bfsArbol(raiz) {
  if (!raiz) return [];
  const cola = [raiz];
  const resultado = [];
  
  while (cola.length > 0) {
    const nodo = cola.shift();
    resultado.push(nodo.val);
    if (nodo.izq) cola.push(nodo.izq);
    if (nodo.der) cola.push(nodo.der);
  }
  return resultado;
}

// Altura del árbol
function altura(nodo) {
  if (!nodo) return 0;
  return 1 + Math.max(altura(nodo.izq), altura(nodo.der));
}

// ¿Es árbol binario de búsqueda?
function esBST(nodo, min = -Infinity, max = Infinity) {
  if (!nodo) return true;
  if (nodo.val <= min || nodo.val >= max) return false;
  return esBST(nodo.izq, min, nodo.val) &&
         esBST(nodo.der, nodo.val, max);
}