Árboles de búsqueda binaria

Árbol de búsqueda binaria (BST)

Un BST es un árbol binario donde para cada nodo: valores del subárbol izquierdo < valor del nodo < valores del subárbol derecho. Esto permite búsqueda O(log n) en árboles balanceados.

Operaciones del BST

class BSTNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new BSTNode(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  search(value) {
    let current = this.root;
    while (current) {
      if (value === current.value) return true;
      current = value < current.value ? current.left : current.right;
    }
    return false;
  }

  findMin() {
    let current = this.root;
    while (current && current.left) current = current.left;
    return current ? current.value : null;
  }

  findMax() {
    let current = this.root;
    while (current && current.right) current = current.right;
    return current ? current.value : null;
  }
}