#include <stdio.h>
#include <conio.h>
#include <alloc.h>

#define MAX 101

struct node
{
    struct node *left ;
    int data ;
    struct node *right ;
} ;

void insert ( struct node **, int ) ;
void preorder ( struct node * ) ;
void postorder ( struct node * ) ;
void inorder ( struct node * ) ;
struct node * recons ( int *, int *, int ) ;
void deltree ( struct node * ) ;

intin[MAX], pre[MAX], x ;

void main( )
{
    struct node *t, *p, *q ;
    int req, i, num ;

    t = NULL ;  /* empty tree */


    clrscr( ) ;
    printf ( "Specify the number of items to be inserted: " ) ;
    while ( 1 )
    {
        scanf ( "%d", &req ) ;
        if ( req >= MAX || req <= 0 )
            printf ( "\nEnter number between 1 to 100.\n" ) ;
        elsebreak ;
    }

    for ( i = 0 ; i < req ; i++ )
    {
        printf ( "Enter the data: " ) ;
        scanf ( "%d", &num ) ;
        insert ( &t, num ) ;
    }

    printf ( "\nIn-order   Traversal:\n" ) ;
    x = 0 ;
    inorder ( t ) ;

    printf ( "\nPre-order  Traversal:\n" ) ;
    x = 0 ;
    preorder ( t ) ;

    printf ( "\nPost-order Traversal:\n" ) ;
    x = 0 ;
    postorder ( t ) ;

    deltree ( t ) ;
    t = NULL ;
    t = recons ( in, pre, req ) ;

    printf ( "\n\nAfter reconstruction of the binary tree.\n" ) ;

    x = 0 ;
    printf ( "\nIn-order   Traversal:\n" ) ;
    inorder ( t ) ;

    x = 0 ;
    printf ( "\nPre-order  Traversal:\n" ) ;
    preorder ( t ) ;
    x = 0 ;
    printf ( "\nPost-order Traversal:\n" ) ;
    postorder ( t ) ;

    deltree ( t ) ;
    getch( ) ;
}

/* inserts a new node in a binary search tree */
void insert ( struct node **sr, int num )
{
    if ( *sr == NULL )
    {
        *sr = ( struct node * ) malloc ( sizeof ( struct node ) ) ;

        ( *sr ) -> left = NULL ;
        ( *sr ) -> data = num ;
        ( *sr ) -> right = NULL ;
        return ;
    }
    else/* search the node to which new node will be attached */

    {
        /* if new data is less, traverse to left */
if ( num < ( *sr ) -> data )
            insert ( &( ( *sr ) -> left ), num ) ;
        else/* else traverse to right */

            insert ( &( ( *sr ) -> right ), num ) ;
    }
}

void preorder ( struct node *t )
{
    if ( t != NULL )
    {
        printf ( "%d\t", pre[x++]= t -> data ) ;
        preorder ( t -> left ) ;
        preorder ( t -> right ) ;
    }
}

void postorder ( struct node *t )
{
    if ( t != NULL )
    {
        postorder ( t -> left ) ;
        postorder ( t -> right ) ;
        printf ( "%d\t", t -> data ) ;
    }
}

void inorder ( struct node *t )
{
    if ( t != NULL )
    {
        inorder ( t -> left ) ;
        printf ( "%d\t", in[x++]= t -> data ) ;
        inorder ( t -> right ) ;
    }
}

struct node * recons ( int *inorder, int *preorder, int noofnodes )
{
    struct node *temp, *left, *right ;
    int tempin[100], temppre[100], i, j ;

    if ( noofnodes == 0 )
        return NULL ;

    temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
    temp -> data = preorder[0] ;
    temp -> left = NULL ;
    temp -> right = NULL ;

    if ( noofnodes == 1 )
        return temp ;
    for ( i = 0 ; inorder[i] != preorder[0] ; )
        i++ ;

    if ( i > 0 )
    {
        for ( j = 0 ; j <= i  ; j++ )
            tempin[j] = inorder[j] ;

        for ( j = 0 ; j < i  ; j++ )
            temppre[j] = preorder[j + 1] ;
    }

    left = recons ( tempin, temppre, i ) ;
    temp -> left = left ;

    if ( i < noofnodes - 1 )
    {
        for ( j = i ; j < noofnodes - 1 ; j++ )
        {
            tempin[j - i] = inorder[j + 1] ;
            temppre[j - i] = preorder[j + 1] ;
        }
    }

    right = recons ( tempin, temppre, noofnodes - i - 1 ) ;
    temp -> right = right ;

    return temp ;
}

void deltree ( struct node *t )
{
    if ( t != NULL )
    {
        deltree ( t -> left ) ;
        deltree ( t -> right ) ;
    }
    free ( t ) ;
}