Árbol binario de búsqueda (BST): inserción, búsqueda y recorridos

Un árbol binario de búsqueda (BST) es una estructura de datos jerárquica que permite operaciones de búsqueda, inserción y eliminación eficientes. Aparece en casi todas las entrevistas técnicas.

La regla del BST

• Subárbol izquierdo: valores menores que el nodo raíz
• Subárbol derecho: valores mayores que el nodo raíz
• Cada subárbol también es un BST

Implementación en Python

class Nodo:
    def __init__(self, valor):
        self.valor = valor
        self.izquierda = None
        self.derecha = None

class BST:
    def __init__(self):
        self.raiz = None
    
    def insertar(self, valor):
        self.raiz = self._insertar(self.raiz, valor)
    
    def _insertar(self, nodo, valor):
        if nodo is None:
            return Nodo(valor)
        if valor  nodo.valor:
            nodo.derecha = self._insertar(nodo.derecha, valor)
        return nodo

Los tres recorridos

Inorden: izquierda → raíz → derecha

def inorden(nodo, resultado=[]):
    if nodo:
        inorden(nodo.izquierda, resultado)
        resultado.append(nodo.valor)
        inorden(nodo.derecha, resultado)
    return resultado
# Resultado: elementos ordenados de menor a mayor

Preorden: raíz → izquierda → derecha

def preorden(nodo, resultado=[]):
    if nodo:
        resultado.append(nodo.valor)  # raíz primero
        preorden(nodo.izquierda, resultado)
        preorden(nodo.derecha, resultado)
    return resultado

Complejidad

Un árbol degenerado ocurre al insertar elementos ya ordenados. Para evitarlo se usan árboles AVL o Red-Black Trees que se auto-balancean.