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

#define PLUS_INFTY 1000000000
#define MINUS_INFTY -1000000000
#define EVEN_PC 0
#define ODD_PC 1
#define ERROR -2

typedef struct _node {
   int key;
   struct _node *L, *R;
} tnode;

typedef tnode *BST;

int count ( int n )
{
   int *C, i, j, cnt;

   if (n < 0) return 0;
   C = (int *)malloc((n + 1) * sizeof(int));
   C[0] = 1;
   for (i=1; i<=n; ++i) {
      C[i] = 0;
      for (j=0; j<i; ++j) C[i] += C[j] * C[i-1-j];
   }
   cnt = C[n];
   free(C);
   return cnt;
}

int ispreorder ( int A[], int i, int j )
{
   int r, k, u, lmax, rmin;

   if (i >= j) return 1;
   r = A[i];
   k = i+1; while ((k <= j) && (A[k] < r)) ++k;
   lmax = MINUS_INFTY; for (u=i+1; u<k; ++u) if (A[u] > lmax) lmax = A[u];
   rmin = PLUS_INFTY; for (u=k; u<=j; ++u) if (A[u] < rmin) rmin = A[u];
   if ((lmax < r) && (r < rmin)) return (ispreorder(A, i+1, k-1) && ispreorder(A, k, j));
   return 0;
}

int ispostorder (  int A[], int i, int j )
{
   int r, k, u, lmax, rmin;

   if (i >= j) return 1;
   r = A[j];
   k = i; while ((k < j) && (A[k] < r)) ++k;
   lmax = MINUS_INFTY; for (u=i; u<k; ++u) if (A[u] > lmax) lmax = A[u];
   rmin = PLUS_INFTY; for (u=k; u<j; ++u) if (A[u] < rmin) rmin = A[u];
   if ((lmax < r) && (r < rmin)) return (ispostorder(A, i, k-1) && ispostorder(A, k, j-1));
   return 0;
}

BST pre2BST ( int A[], int i, int j )
{
   int r, k;
   BST p;

   if (i > j) return NULL;
   r = A[i];
   k = i+1; while ((k <= j) && (A[k] < r)) ++k;
   p = (tnode *)malloc(sizeof(tnode));
   p -> key = r;
   p -> L = pre2BST(A, i+1, k-1);
   p -> R = pre2BST(A, k, j);
   return p;
}

BST post2BST ( int A[], int i, int j )
{   int r, k;
   BST p;

   if (i > j) return NULL;
   r = A[j];
   k = i; while ((k < j) && (A[k] < r)) ++k;
   p = (tnode *)malloc(sizeof(tnode));
   p -> key = r;
   p -> L = post2BST(A, i, k-1);
   p -> R = post2BST(A, k, j-1);
   return p;
}

void genperms ( int A[], int n, int i, BST *L, int *last, int parity )
{
   int j, k, t, *B;

   if (i == n-1) {
      if (parity == EVEN_PC) {
         if (ispreorder(A,0,n-1)) {
            L[*last] = pre2BST(A,0,n-1);
            ++(*last);
         }
      } else if (parity == ODD_PC) {
         if (ispostorder(A,0,n-1)) {
            L[*last] = post2BST(A,0,n-1);
            ++(*last);
         }
      }
   }

   B = (int *)malloc(n * sizeof(int));
   for (k=0; k<n; ++k) B[k] = A[k];
   for (j=i; j<n; ++j) {
      t = A[j];
      for (k=j; k>i; --k) A[k] = A[k-1];
      A[i] = t;
      genperms(A,n,i+1,L,last,parity);
      for (k=i; k<=j; ++k) A[k] = B[k];
   }
   free(B);
}

BST *allBST ( int n, int parity )
{
   BST *L;
   int *A, i, last;

   L = (BST *)malloc(count(n) * sizeof(BST));
   A = (int *)malloc(n * sizeof(int));
   for (i=0; i<n; ++i) A[i] = i+1;
   last = 0;
   genperms(A,n,0,L,&last,parity);
   printf("\n+++ %d trees created\n", last);
   return L;
}

void preorder ( BST T )
{
   if (T == NULL) return;
   printf(" %d", T -> key);
   preorder(T -> L);
   preorder(T -> R);
}

void postorder ( BST T )
{
   if (T == NULL) return;
   postorder(T -> L);
   postorder(T -> R);
   printf(" %d", T -> key);
}

void preorderarr ( BST T, int B[], int *last )
{
   if (T == NULL) return;
   B[*last] = T -> key; ++(*last);
   preorderarr(T -> L, B, last);
   preorderarr(T -> R, B, last);
}

void postorderarr ( BST T, int B[], int *last )
{
   if (T == NULL) return;
   postorderarr(T -> L, B, last);
   postorderarr(T -> R, B, last);
   B[*last] = T -> key; ++(*last);
}

int ordcomp ( int A[], int n, BST T, int parity )
{
   int *B, last, i, retval;

   B = (int *)malloc(n * sizeof(int));
   for (i=0; i<n; ++i) B[i] = -1;
   last = 0;
   if (parity == EVEN_PC) preorderarr(T,B,&last);
   else postorderarr(T,B,&last);
   if (last != n) retval = ERROR;
   else {
      retval = 0;
      for (i=0; i<n; ++i) {
         if (A[i] < B[i]) { retval = -1; break; }
         if (A[i] > B[i]) { retval = 1; break; }
      }
   }
   free(B);
   return retval;
}

int binsearch ( BST *L, int cnt, int A[], int n, int parity )
{
   int l, r, m, c;

   l = 0; r = cnt - 1;
   while (l <= r) {
      m = (l + r) / 2;
      c = ordcomp(A,n,L[m],parity);
      if (c == ERROR) return ERROR;
      if (c == 0) return m;
      if (c == -1) r = m - 1;
      if (c == 1) l = m + 1;
   }
   return -1;
}

void randperm ( int A[], int n )
{
   int i, j, t;

   for (i=0; i<n; ++i) A[i] = i+1;
   for (i=n-1; i>=1; --i) {
      j = rand() % (i+1);
      if (j != i) { t = A[i]; A[i] = A[j]; A[j] = t; }
   }
}

void searchcases ( BST *L, int cnt, int n, int parity )
{
   int *A, i, searchres;

   A = (int *)malloc(n * sizeof(int));

   searchres = -1;
   while (searchres < 0) {
      randperm(A,n);
      searchres = binsearch(L,cnt,A,n,parity);
   }
   printf("\n+++ Search :"); for (i=0; i<n; ++i) printf(" %d", A[i]);
   printf(" : Tree # %d matches\n", searchres+1);

   searchres = 0;
   while (searchres != -1) {
      randperm(A,n);
      searchres = binsearch(L,cnt,A,n,parity);
   }
   printf("+++ Search :"); for (i=0; i<n; ++i) printf(" %d", A[i]);
   printf(" : Tree not found\n");

   free(A);
}

int main ( int argc, char *argv[] )
{
   int n, i, cnt;
   BST *L0, *L1;

   srand((unsigned int)time(NULL));
   if (argc > 1) n = atoi(argv[1]); else scanf("%d", &n);
   printf("n = %d\n", n);

   cnt = count(n);

   printf("\n\n******************************** E V E N   P C ********************************\n");
   printf("+++ Count of BSTs = %d\n", cnt);

   L0 = allBST(n,EVEN_PC);
   printf("\n+++ The preorder listings of the BSTs\n");
   for (i=0; i<cnt; ++i) {
      printf("    BST # %4d :", i+1); preorder(L0[i]); printf("\n");
   }

   searchcases(L0,cnt,n,EVEN_PC);

   printf("\n\n********************************* O D D   P C *********************************\n");
   printf("+++ Count of BSTs = %d\n", cnt);

   L1 = allBST(n,ODD_PC);
   printf("\n+++ The postorder listings of the BSTs\n");
   for (i=0; i<cnt; ++i) {
      printf("    BST # %4d :", i+1); postorder(L1[i]); printf("\n");
   }

   searchcases(L1,cnt,n,ODD_PC);

   exit(0);
}