Encuentra el ancestro común más cercano en un árbol de búsqueda binaria.

Anfoque recursivo

struct NodoArbol {
    int valor;
    NodoArbol* izquierda;
    NodoArbol* derecha;
    NodoArbol(int x) : valor(x), izquierda(nullptr), derecha(nullptr) {}
};

NodoArbol* encontrarAncestro(NodoArbol* raiz, NodoArbol* nodo1, NodoArbol* nodo2) {
    if (!raiz) return nullptr;
    
    if (nodo1->valor < raiz->valor && nodo2->valor < raiz->valor) {
        NodoArbol* resultado = encontrarAncestro(raiz->izquierda, nodo1, nodo2);
        if (resultado) return resultado;
    }
    
    if (nodo1->valor > raiz->valor && nodo2->valor > raiz->valor) {
        NodoArbol* resultado = encontrarAncestro(raiz->derecha, nodo1, nodo2);
        if (resultado) return resultado;
    }
    
    return raiz;
}

Enfoque iterativo

NodoArbol* encontrarAncestroIterativo(NodoArbol* raiz, NodoArbol* nodo1, NodoArbol* nodo2) {
    while (raiz) {
        if (raiz->valor > nodo1->valor && raiz->valor > nodo2->valor) {
            raiz = raiz->izquierda;
        } else if (raiz->valor < nodo1->valor && raiz->valor < nodo2->valor) {
            raiz = raiz->derecha;
        } else {
            return raiz;
        }
    }
    return nullptr;
}

LeetCode 701

Inserción en árbol de búsqueda binaria.

Enfoque recursivo

struct NodoArbol {
    int valor;
    NodoArbol* izquierda;
    NodoArbol* derecha;
    NodoArbol(int x) : valor(x), izquierda(nullptr), derecha(nullptr) {}
};

NodoArbol* insertar(NodoArbol* raiz, int valor) {
    if (!raiz) {
        return new NodoArbol(valor);
    }
    
    if (valor < raiz->valor) {
        raiz->izquierda = insertar(raiz->izquierda, valor);
    } else {
        raiz->derecha = insertar(raiz->derecha, valor);
    }
    
    return raiz;
}

Enfoque iterativo

NodoArbol* insertarIterativo(NodoArbol* raiz, int valor) {
    if (!raiz) {
        return new NodoArbol(valor);
    }
    
    NodoArbol* actual = raiz;
    NodoArbol* padre = nullptr;
    
    while (actual) {
        padre = actual;
        if (valor < actual->valor) {
            actual = actual->izquierda;
        } else {
            actual = actual->derecha;
        }
    }
    
    if (valor < padre->valor) {
        padre->izquierda = new NodoArbol(valor);
    } else {
        padre->derecha = new NodoArbol(valor);
    }
    
    return raiz;
}

LeetCode 450

Eliminación de nodo en árbol de búsqueda binaria.

Implementación

struct NodoArbol {
    int valor;
    NodoArbol* izquierda;
    NodoArbol* derecha;
    NodoArbol(int x) : valor(x), izquierda(nullptr), derecha(nullptr) {}
};

NodoArbol* eliminar(NodoArbol* raiz, int clave) {
    if (!raiz) return nullptr;
    
    if (raiz->valor == clave) {
        if (!raiz->izquierda && !raiz->derecha) {
            delete raiz;
            return nullptr;
        }
        
        if (!raiz->izquierda) {
            NodoArbol* temp = raiz->derecha;
            delete raiz;
            return temp;
        }
        
        if (!raiz->derecha) {
            NodoArbol* temp = raiz->izquierda;
            delete raiz;
            return temp;
        }
        
        NodoArbol* minimo = encontrarMinimo(raiz->derecha);
        raiz->valor = minimo->valor;
        raiz->derecha = eliminar(raiz->derecha, minimo->valor);
    } else if (clave < raiz->valor) {
        raiz->izquierda = eliminar(raiz->izquierda, clave);
    } else {
        raiz->derecha = eliminar(raiz->derecha, clave);
    }
    
    return raiz;
}

NodoArbol* encontrarMinimo(NodoArbol* nodo) {
    while (nodo->izquierda) {
        nodo = nodo->izquierda;
    }
    return nodo;
}