Construcción y validación de un Árbol de Búsqueda Binaria en JavaScript

Construir un árbol binario de búsqueda en JavaScript es más sencillo cuando dominas la regla central: en un binary search tree, los valores menores van siempre al lado izquierdo y los mayores al lado derecho. Aquí verás cómo detectar errores lógicos, modelar nodos y programar el método de insert con validaciones claras.

¿Qué corrige la lógica de un binary search tree?

La confusión inicial surge cuando alguna rama rompe la regla de orden. Si un nodo que debería aumentar aparece a la izquierda o uno que debería disminuir aparece a la derecha, el árbol queda mal formado. La lógica debe aplicarse a todas las ramas, no solo a nivel inmediato del root.

• Si los nodos a la derecha no incrementan, la estructura es incorrecta.
• Si los nodos a la izquierda no disminuyen, la estructura es incorrecta.
• La validación debe repetirse en cada nivel del árbol.

¿Qué árbol de ejemplo vamos a formar?

Se construye un árbol con root 10; hijos 4 y 20; y, en niveles siguientes, 2, 8, 17 y 170. La forma correcta respeta el orden:

• Izquierda del 10: 4, y a su vez 2 y 8.
• Derecha del 10: 20, y a su vez 17 y 170.
• Así, los valores a la derecha siempre aumentan y a la izquierda siempre disminuyen.

¿Cómo se modela el nodo y el árbol en JavaScript?

Cada nodo tiene tres propiedades: left, right y value. El árbol mantiene una referencia al root para iniciar recorridos e inserciones.

// Nodo: left, right, value
class Node {
  constructor(value) {
    this.left = null;
    this.right = null;
    this.value = value;
  }
}

// Árbol: referencia a root e inserción de valores
class BinarySearchTree {
  constructor() {
    this.root = null; // inicia sin root
  }

  insert(value) {
    const newNode = new Node(value);

    // Caso 1: árbol vacío → newNode es root
    if (this.root === null) {
      this.root = newNode;
      return this; // importante para romper el flujo
    }

    // Caso 2: árbol con elementos → recorrer
    let currentNode = this.root; // *current node*
    while (true) { // *loop* iterativo
      if (value < currentNode.value) {
        // Ir a la izquierda
        if (!currentNode.left) {
          currentNode.left = newNode;
          return this;
        }
        currentNode = currentNode.left;
      } else {
        // Ir a la derecha
        if (!currentNode.right) {
          currentNode.right = newNode;
          return this;
        }
        currentNode = currentNode.right;
      }
    }
  }
}

• Se usa una class para el árbol y otra para el nodo.
• El constructor del árbol inicia con this.root = null.
• El insert crea un new Node(value) y valida si el árbol está vacío.
• El recorrido usa un while (true) y rompe con return this al insertar.
• La decisión izquierda/derecha depende de value < currentNode.value.

¿Cómo funciona el método insert y el recorrido con while?

El método de insert cubre dos escenarios: crear el root y, si ya existe, recorrer la estructura hasta encontrar el hueco correcto. El recorrido es totalmente guiado por comparaciones menor/mayor.

• Menor que el nodo actual: ir a left. Si left es null, insertar ahí.
• Mayor o igual que el nodo actual: ir a right. Si right es null, insertar ahí.
• En ambos casos, si existe un hijo, mover el current node y continuar el loop.

¿Cómo probar la inserción y validar la estructura?

Prueba rápida en JS creando una instancia del árbol y agregando valores en orden.

const tree = new BinarySearchTree();

tree.insert(10); // root

tree.insert(4);
tree.insert(20);

tree.insert(2);
tree.insert(8);
tree.insert(17);
tree.insert(170);

Resultados esperados al inspeccionar:

• root.value es 10.
• root.left.value es 4 y sus hijos son 2 y 8.
• root.right.value es 20 y sus hijos son 17 y 170.

¿Qué habilidades y conceptos refuerzas con este ejercicio?

• Invariantes de estructura en un binary search tree.
• Modelado con class y constructor en JavaScript.
• Recorrido iterativo con while y control de flujo con return.
• Comparaciones y asignación condicional para izquierda/derecha.
• Manejo de null y uso de variables temporales como current node.

¿Qué sigue con el método search?

El siguiente paso es programar search: recibe un número y devuelve el nodo completo donde se encuentra (incluyendo sus hijos). La lógica de recorrido es muy similar a la de insert, solo que aquí no insertas: comparas y avanzas hasta encontrar o no el valor.

¿Te animas a implementar search? Compártelo en comentarios para que todos veamos tu enfoque y podamos aprender juntos.