BetterAlgo

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

struct stack{
    struct stack* Top;
    void * elem;
};
typedef struct stack* Stack;

struct tree{
    int K;
    struct tree* Dx;
    struct tree* Sx;
};
typedef struct tree* Tree;


Stack pop(Stack S){
    if(S != NULL){
        Stack tmp=S;
        S= S->Top;
        free(tmp);
    }
    return S;
}

Stack push(Stack S, void * E){
    Stack TMP=NULL;
    if( S == NULL ){
        TMP=(Stack)malloc(sizeof(struct stack));
        TMP->elem= E;
        TMP->Top=NULL;
    }
    else{
        TMP=(Stack)malloc(sizeof(struct stack));
        TMP->elem= E;
        TMP->Top= S;

    }
    return TMP;
}

void * top(Stack S){
    if(S != NULL){
        return S->elem;
    }
    return NULL;
}

Tree addDx(Tree T, int K){
    if(T == NULL){
        T= (Tree)malloc(sizeof(struct tree));
        T->K=K;
        T->Dx= NULL;
        T->Sx= NULL;
    }
    else{
        T->Dx= addDx(T->Dx, K);
    }
    return T;
}

Tree addSx(Tree T, int K){
    if(T == NULL){
        T= (Tree)malloc(sizeof(Tree));
        T->K=K;
        T->Dx= NULL;
        T->Sx= NULL;
    }
    else{
        T->Sx= addSx(T->Sx, K);
    }
    return T;
}

Tree AlgoRic(Tree T, int L){
    Tree X=NULL;
    if( T != NULL && L >= 0){
        X= (Tree)malloc(sizeof(struct tree));
        X->K= T->K;
        if ( T->Dx != NULL ){
            X->Dx= AlgoRic(T->Dx, L-1);
        }
        if( T->Sx != NULL ){
            X->Sx= AlgoRic(T->Sx, L-1);
        }
        printf("%d(%p) DX:%p SX:%p\n", X->K, X, X->Dx, X->Sx);
        return X;
    }
}

Tree AlgoIt(Tree T, int L){
    Stack S_x=NULL, S_t=NULL;
    Tree currT=T;
    Tree nextT=NULL;
    Tree X= NULL;
    Tree ret= NULL;
    int currL=L;
    int nextL=0;
    int side;

    while(currT != NULL || S_x != NULL){
        if(currT != NULL){
            printf("CURR:%d", currT->K);
        }
        if(currT != NULL && currL >= 0){
                X= (Tree)malloc(sizeof(struct tree));
                X->K= currT->K;
                if(currT->Dx != NULL){
                    S_x=push(S_x,(void*) X);
                    S_t=push(S_t,(void*) currT);
                    nextT= currT->Dx;
                    nextL= currL-1;
                    side=0;

                }
                else if( currT->Sx != NULL){
                    S_x=push(S_x,(void*) X);
                    S_t=push(S_t,(void*) currT);
                    nextT= currT->Sx;
                    nextL= currL-1;
                    side=1;
                }
                else{
                    ret=X;
                    nextT=NULL;
                    nextL=currL-1;
                }
        }
        else{

            currT=(Tree)top(S_t);
            X=(Tree) top(S_x);
            S_x=pop(S_x);
            currL=currL+1;

            if(side == 0){
                X->Dx= ret;
                if(currT->Sx != NULL){
                    S_x=push(S_x, (void*) X);
                    nextT=currT->Sx;
                    nextL=currL-1;
                }
                else{
                    S_t=pop(S_t);
                    ret=X;
                    nextT=NULL;
                    nextL=currL;
                }
            }
            else{
                nextT= NULL;
                nextL=currL;
                X->Sx=ret;
                S_t=pop(S_t);
            }
        }
        currL=nextL;
        currT=nextT;
    }
    return X;
}

int main(){
    Tree t= NULL;
    t= addDx(t, 1);
    t= addDx(t, 3);
    t= addDx(t, 6);
    t= addDx(t, 5);
    t= addSx(t, 2);
    t= addSx(t, 4);

    printf("OUTPUT 1:\n");
    AlgoRic(t, 3);
    printf("----EOF-----\n\n");
    printf("OUTPUT 2:\n");
    AlgoIt(t, 3);
    printf("----EOF-----\n\n");

}