Binary Search Tree with Level Order Traversal

bstwithlot.c

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


/*********************** TREE ************************/
typedef struct _tnode{
    int value;
    struct _tnode *left;
    struct _tnode *right;
} tnode;

typedef tnode Tree;

tnode * newTNode(int X){

    tnode * temp;
    temp = (tnode *)malloc(sizeof(tnode));
    temp->value = X;
    temp->left = temp->right = NULL;
    return temp;
}

tnode * FindMin(Tree * T){

    if(T!=NULL)
        while(T->left!=NULL)
            T = T->left;
    return T;
}

tnode * FindMax(Tree * T){

    if(T!=NULL)
        while(T->right!=NULL)
            T = T->right;
    return T;
}

Tree * Insert(int X, Tree * T){

if(T == NULL)
    return newTNode(X);
else{

    if(X > T->value)
        T->right = Insert(X, T->right);

    else if(X < T->value)
        T->left = Insert(X, T->left);

}
return T;
}

Tree * Delete(int X, Tree * T){

    tnode * temp;

    if(X > T->value)
        T->right = Delete(X,T->right);

    else if( X < T->value)
        T->left = Delete(X,T->left);

    else if( T->left && T->right)
    {
        temp = FindMin(T->right);
        T->value = temp->value;
        T->right = Delete(T->value,T->right);
    }
    else
    {   temp = T;
        if(T->left == NULL)
            T = T->right;
        else if(T->right == NULL)
            T = T->left;
        free(temp);
    }

    return T;
}

/*********************** QUEUE ************************/

typedef struct _qnode{
    tnode * data;
    int level;
    struct _qnode *next;
} qnode;

typedef enum {false = 0, true} bool;

bool isQEmpty(qnode **front, qnode **rear){

        if( (*front == *rear) && (*rear == NULL) ){
            //printf("Queue Empty\n");
            return true;
        }

        //printf("Queue Not Empty\n");
        return false;
}

void printQueue(qnode ** front){

    qnode * temp;
    temp = *front;
    printf("Queue: ");
    while(temp!=NULL){
    printf("%d ", temp->data->value);
    temp = temp->next;
    }
    printf("\n");
}

qnode * newQNode(tnode * data, int level){


    qnode * temp;
    temp = (qnode *)malloc(sizeof(qnode));
    temp->data = data;
    temp->level = level;
    temp->next = NULL;

    //printf("Prepared node %d for Enqueue\n",temp->data->value);

    return temp;

}

void Enqueue(qnode **front, qnode **rear, qnode * ndata){

    //printf("Adding %d to Queue\n",ndata->data->value);

    if(*rear == NULL){
         //printf("Queue is null\n");
        *rear = ndata;
        *front = *rear;
    }
    else{
        (*rear)->next = ndata;
        *rear = ndata;
    }

    //printQueue(&(*front));
}

qnode * Dequeue(qnode **front, qnode **rear){

    qnode * temp = NULL;


    temp = *front;
    *front = temp->next;

    if(temp == *rear){
        *rear = *front;
    }

    //printf("Dequeued %d\n",temp->data->value);
    return temp;
}


/******************** PRINT TREE *************************/


void printTree(Tree * T){

qnode *front, *rear, *temp;
front = rear = temp = NULL;
int level = -1;

printf("\nTree: \n");

Enqueue(&front, &rear, newQNode(T,0));

while(!isQEmpty(&front,&rear)){

temp = Dequeue(&front, &rear);

if(level != temp->level){
printf("\n Level %d : ",temp->level);
level = temp->level;
}
printf("%d ", temp->data->value);


if(temp->data->left != NULL)
Enqueue(&front,&rear,newQNode(temp->data->left,temp->level+1 ));
if(temp->data->right != NULL)
Enqueue(&front,&rear,newQNode(temp->data->right,temp->level+1 ));

}

printf("\n");

}

/*********************** MAIN ************************/

int main(){

Tree * T = NULL;

int arr[] = {10,6,13,5,7,11,14};
int i = 0;

for(i=0; i<7;i++)
 T = Insert(arr[i],T);

printTree(T);

T = Delete(6,T);

printTree(T);

return 0;
}