#include <stdio.h>
#include <stdlib.h>

typedef struct Nodo {
    struct Nodo *left;
    struct Nodo *right;
    int info;
} nodo;

typedef struct Stack {
    nodo **listanodi;
    int length;
    int index;
} stack;

typedef nodo* tree;

stack* NEW_STACK(int length) {
    stack *s = (stack*)malloc(sizeof(stack));
    s->index = -1;
    s->length = length;
    s->listanodi = (nodo**)malloc(length*sizeof(nodo*));

    printf("Creato stack\n");

    return s;
}

void PRINT_STACK(stack *s) {
    printf("Stack punta a indirizzo %p\n",s->listanodi);

    printf("Stampo stack\n");
    for(int i=0;i<s->index;i++) {
        printf("[%d]=>%p\n",i,s->listanodi[i]);
    }
}

nodo* POP(stack **s) { /* elimina elemento dallo stack */
    nodo* last = ((*s)->listanodi)[(*s)->index];
    //printf("Estratto %p\n",last);

    (*s)->index--;
    return last;
}

void PUSH(stack **s, nodo *nodo) { /* inserisce nuovo elemento nello stack */
    if((*s)->index==(*s)->length-1) return; // stack pieno

    //printf("%p\n",nodo); // stampa indirizzo root
    (*s)->index = (*s)->index+1;

    ((*s)->listanodi)[(*s)->index] = nodo;
}

nodo *CREA_NODO(int info) { // crea un nodo
    nodo *temp = (nodo*)malloc(sizeof(nodo));
    temp->info = info;
    temp->right = NULL;
    temp->left = NULL;

    return temp;
}

void ADD_NODO_RIC(nodo **nodo,int info) { // aggiunge un nodo all'albero binario
    if(*nodo == NULL) {
        printf("Nuovo nodo %d\n",info);
        *nodo = CREA_NODO(info);
        return;
    }

    if((*nodo)->info < info) { // se nodo ha valore maggiore
        ADD_NODO_RIC(&((*nodo)->right),info);
    } else {
        ADD_NODO_RIC(&((*nodo)->left),info);
    }
}


void ADD_NODO(tree *t,int info) {
    ADD_NODO_RIC(t,info);
}

void PRINT_ALBERO(nodo *root) {
    nodo *nodo = root;

    if(root==NULL) return; // albero vuoto

    stack *stack = NEW_STACK(30);
    PUSH(&stack,NULL);

    printf("Stampo albero:\n");

    do { // fino a quando non viene esplorato tutto l'albero
        if(nodo != NULL) {
            PUSH(&stack,nodo);
            nodo = nodo->left;
        } else { // figlio sinistro = NULL
            nodo = POP(&stack);

            while(nodo->right == NULL) {
                printf("%d \n",nodo->info);
                nodo = POP(&stack);
            }

            printf("%d\n",nodo->info);

            nodo = nodo->right;
        }
    } while(stack->index != -1);
}