#include 
#include 

typedef struct Nodo {
    int dato;
    struct Nodo *izq;
    struct Nodo *der;
} Nodo;

Nodo* crearNodo(int valor) {
    Nodo *nuevo = (Nodo*)malloc(sizeof(Nodo));
    nuevo->dato = valor;
    nuevo->izq = NULL;
    nuevo->der = NULL;
    return nuevo;
}

Nodo* insertarConMensaje(Nodo *raiz, int valor, int esPrimerNodo) {
    if (raiz == NULL) {
        if (esPrimerNodo) {
            printf("Ingresa %d al arbol. Su padre es NULL.\n", valor);
        }
        return crearNodo(valor);
    }
    
    if (valor < raiz->dato) {
        if (raiz->izq == NULL) {
            printf("Ingresa %d al arbol. Su padre es el %d. Es su hijo izquierdo.\n", valor, raiz->dato);
        }
        raiz->izq = insertarConMensaje(raiz->izq, valor, 0);
    } else if (valor > raiz->dato) {
        if (raiz->der == NULL) {
            printf("Ingresa %d al arbol. Su padre es el %d. Es su hijo derecho.\n", valor, raiz->dato);
        }
        raiz->der = insertarConMensaje(raiz->der, valor, 0);
    }
    
    return raiz;
}

Nodo* insertar(Nodo *raiz, int valor) {
    int esPrimero;
    if (raiz == NULL) {
        esPrimero = 1;
    } else {
        esPrimero = 0;
    }
    return insertarConMensaje(raiz, valor, esPrimero);
}

void imprimirArbolAux(Nodo *raiz, int espacio) {
    int i;
    if (raiz == NULL) {
        return;
    }
    
    espacio += 5;
    imprimirArbolAux(raiz->der, espacio);
    
    printf("\n");
    for (i = 5; i < espacio; i++) {
        printf(" ");
    }
    printf("%d\n", raiz->dato);
    
    imprimirArbolAux(raiz->izq, espacio);
}

void verArbol(Nodo *raiz) {
    if (raiz == NULL) {
        printf("El arbol esta vacio.\n");
        return;
    }
    printf("\nEstructura del Arbol:\n");
    imprimirArbolAux(raiz, 0);
    printf("\n");
}

void inOrden(Nodo *raiz, int *vector, int *index) {
    if (raiz != NULL) {
        inOrden(raiz->izq, vector, index);
        vector[(*index)++] = raiz->dato;
        inOrden(raiz->der, vector, index);
    }
}

void ordenarVector(Nodo *raiz, int *vector, int tam) {
    int index = 0;
    inOrden(raiz, vector, &index);
}

void imprimirVector(int *vector, int tam) {
    int i;
    printf("Vector: [ ");
    for (i = 0; i < tam; i++) {
        printf("%d ", vector[i]);
    }
    printf("]\n");
}

void espejoArbol(Nodo *raiz) {
    Nodo *temp;
    if (raiz == NULL) {
        return;
    }
    
    temp = raiz->izq;
    raiz->izq = raiz->der;
    raiz->der = temp;
    
    espejoArbol(raiz->izq);
    espejoArbol(raiz->der);
}

void liberarArbol(Nodo *raiz) {
    if (raiz != NULL) {
        liberarArbol(raiz->izq);
        liberarArbol(raiz->der);
        free(raiz);
    }
}

int main() {
    Nodo *raiz = NULL;
    int opcion, tam, i;
    int *vector = NULL;
    int arbolCreado = 0;
    
    printf("=== ARBOL BINARIO DE BUSQUEDA ===\n\n");
    
    do {
        printf("\n--- MENU ---\n");
        printf("1. Insertar elementos desde vector\n");
        printf("2. Ver Arbol\n");
        printf("3. Ordenar vector\n");
        printf("4. Imprimir Vector\n");
        printf("5. Espejo del Arbol\n");
        printf("6. Salir\n");
        printf("Opcion: ");
        
        if (scanf("%d", &opcion) != 1) {
            while(getchar() != '\n');
            printf("Error: Ingrese solo numeros.\n");
            continue;
        }
        
        switch(opcion) {
            case 1:
                if (arbolCreado) {
                    printf("El arbol ya fue creado. Liberando arbol anterior...\n");
                    liberarArbol(raiz);
                    free(vector);
                    raiz = NULL;
                }
                
                printf("Ingrese la cantidad de elementos: ");
                scanf("%d", &tam);
                
                vector = (int*)malloc(tam * sizeof(int));
                
                printf("Ingrese los %d elementos:\n", tam);
                for (i = 0; i < tam; i++) {
                    printf("Elemento %d: ", i + 1);
                    scanf("%d", &vector[i]);
                    raiz = insertar(raiz, vector[i]);
                }
                
                arbolCreado = 1;
                printf("\nArbol creado exitosamente!\n");
                imprimirVector(vector, tam);
                break;
                
            case 2:
                if (!arbolCreado) {
                    printf("Primero debe crear el arbol (opcion 1).\n");
                } else {
                    verArbol(raiz);
                }
                break;
                
            case 3:
                if (!arbolCreado) {
                    printf("Primero debe crear el arbol (opcion 1).\n");
                } else {
                    ordenarVector(raiz, vector, tam);
                    printf("\nVector ordenado exitosamente!\n");
                }
                break;
                
            case 4:
                if (!arbolCreado) {
                    printf("Primero debe crear el arbol (opcion 1).\n");
                } else {
                    imprimirVector(vector, tam);
                }
                break;
                
            case 5:
                if (!arbolCreado) {
                    printf("Primero debe crear el arbol (opcion 1).\n");
                } else {
                    espejoArbol(raiz);
                    printf("\nEspejo del arbol creado exitosamente!\n");
                    verArbol(raiz);
                }
                break;
                
            case 6:
                printf("\nSaliendo del programa...\n");
                if (arbolCreado) {
                    liberarArbol(raiz);
                    free(vector);
                }
                break;
                
            default:
                printf("Opcion invalida. Intente de nuevo.\n");
        }
        
    } while(opcion != 6);
    
    return 0;
}