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

struct Node
{
    int Element;
    struct Node* Left;
    struct Node* Right;
};

typedef struct Node* TNode;

TNode MakeEmpty( TNode T )
{
    if( T != NULL )
    {
        MakeEmpty( T->Left );
        MakeEmpty( T->Right );
        free( T );
    }
    return NULL;
}

TNode Find( int X, TNode T )
{
    if( T == NULL)
        return NULL;
    else if( X < T->Element )
        return Find( X, T->Left );
    else if( X > T->Element )
        return Find( X, T->Right );
    else
        return T;
}

TNode FindMin( TNode T )
{
    if( T == NULL)
        return NULL;
    else if( T -> Left == NULL)
        return T;
    else
        return FindMin( T->Left );
}

TNode FindMax( TNode T )
{
    if( T == NULL)
        return NULL;
    else if( T -> Right == NULL)
        return T;
    else
        return FindMax( T->Right);
}

TNode Insert( int X, TNode T )
{
    if( T == NULL) //create and return a 1-node tree
    {
        //printf("Cretaea a node\n");
        T = (struct Node*)malloc( sizeof( struct Node ) );
        if( T == NULL)
            printf("Out of space");
        else
        {
            T->Element = X;
            T->Left = T->Right = NULL;

            //printf("the element in the node is %d\n", T->Element);
        }
    }
    else if( X < T->Element )
    {
        T->Left = Insert( X, T->Left);
    }
    else if( X > T->Element)
    {
        T->Right = Insert( X, T->Right );//else, X is in the tree already; do nothing
    }
    return T;
}

TNode Delete( int X, TNode T )
{
    TNode TmpCell;
    if( T == NULL )
        printf( "Element not found" );
    else if( X < T->Element )  /* Go left */
        T->Left = Delete( X, T->Left );
    else if( X > T->Element )  /* Go right */
        T->Right = Delete( X, T->Right );
    else  /* Found element to be deleted */
        if( T->Left && T->Right )
            /* Two children */
        {
            /* Replace with smallest in right subtree */
            TmpCell = FindMin( T->Right );
            T->Element = TmpCell->Element;
            T->Right = Delete( T->Element, T->Right );
        }
        else  /* One or zero children */
        {
            TmpCell = T;
            if( T->Left == NULL )
                /* Also handles 0 children */
                T = T->Right;
            else if( T->Right == NULL )
                T = T->Left;
            free( TmpCell );
        }
    return T;
} //end of Delete routine


void PrintInorder(TNode t)
{

    if(t==NULL)
        return;

    PrintInorder(t->Left);
    printf("Node: %d\n", t->Element);
    PrintInorder(t->Right);

}

void PrintPreorder(TNode t)
{

    if(t==NULL)
        return;

    printf("Node: %d\n", t->Element);
    PrintInorder(t->Left);
    PrintInorder(t->Right);

}

void PrintPostorder(TNode t)
{

    if(t==NULL)
        return;

    PrintInorder(t->Left);
    PrintInorder(t->Right);
    printf("Node: %d\n", t->Element);


}

int main()
{
    TNode tree1;
    tree1=NULL;

    tree1=MakeEmpty(tree1);

    tree1=Insert(10, tree1);
    Insert(20, tree1);
    Insert(50, tree1);
    Insert(5, tree1);
    printf("%d\n", tree1->Element);

    printf("Inorder...\n");
    PrintInorder(tree1);

    printf("Preorder...\n");
    PrintPreorder(tree1);

    printf("Postorder...\n");
    PrintPostorder(tree1);

    MakeEmpty(tree1);
    return 0;
}