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

struct tree
{
    struct tree *left;
    struct tree *right;
    int value;
};

typedef struct tree node;

void insertNode(node **root, int val)
{
    node *temp = NULL;
    if(!(*root))
    {
        temp = (node*) malloc(sizeof(node));
        temp->value = val;
        temp->left = NULL;
        temp->right = NULL;
        *root = temp;
    }

    if(val < (*root)->value)
        insertNode(&(*root)->left, val);

    if(val >= (*root)->value)
        insertNode(&(*root)->right, val);
}

void preOrder(node *root)
{
    if(root)
    {   printf(" %d",root->value);
        preOrder(root->left);
        preOrder(root->right);
    }
}

void inOrder(node *root)
{
    if(root)
    {
        inOrder(root->left);
        printf(" %d",root->value);
        inOrder(root->right);
    }
}

void postOrder(node *root)
{
    if(root)
    {
        postOrder(root->left);
        postOrder(root->right);
        printf(" %d",root->value);
    }
}

void delTree(node *root)
{
    if(root)
    {
        delTree(root->left);
        delTree(root->right);
        free(root);
    }
}

int main()
{
    int val;
    char ch; ch = 'y';
    node *root;

    while(ch == 'y')
    {
        scanf("Enter the node value: %d", &val);
        insertNode(&root, val);
        scanf("Want to enter more: %c", &ch);
    }

    printf("\nInOrder traversal:\n");
    inOrder(root);
    printf("\nPreOrder traversal:\n");
    preOrder(root);
    printf("\nPostOrder traversal:\n");
    postOrder(root);

    delTree(root);
    printf("Tree Deleted.");

    return 0;
}