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

typedef struct _node {
   int key;
   struct _node *left;
   struct _node *right;
} node;

void printtree ( node *T, int level )
{
   int i;

   if (T) {
      printtree(T->left, level+1);
      printf("    ");
      if (level > 0) {
         for (i=0; i<level; ++i) printf("    ");
      }
      printf("%3d\n", T -> key);
      printtree(T->right, level+1);
   }
}

void printlist ( node *list )
{
   int i;

   if (list == NULL) return;

   i = 0;
   while (1) {
      if (i % 19 == 0) printf("    ");
      printf("%3d ", list -> key);
      ++i;
      if (i % 19 == 0) printf("\n");
      if (list -> right == NULL) break;
      list = list -> right;
   }
   if (i % 19) printf("\n");

   i = 0;
   while (list) {
      if (i % 19 == 0) printf("    ");
      printf("%3d ", list -> key);
      ++i;
      if (i % 19 == 0) printf("\n");
      list = list -> left;
   }
   if (i % 19) printf("\n");
}

node *BSTinsert ( node *T, int a )
{
   node *p, *q;

   p = NULL; q = T;
   while (q) {
      if (a == q -> key) return T;
      p = q;
      if (a < q -> key) q = q -> left; else q = q -> right;
   }
   q = (node *)malloc(sizeof(node));
   q -> key = a; q -> left = q -> right = NULL;
   if (p == NULL) return q;
   if (a < p -> key) p -> left = q; else p -> right = q;
   return T;
}

node *genBST ( int n )
{
   int i, a;
   node *T;

   T = NULL;
   for (i=0; i<n; ++i) {
      if (i % 19 == 0) printf("    ");
      a = rand() % 1000;
      printf("%3d ", a);
      if (i % 19 == 18) printf("\n");
      T = BSTinsert(T,a);
   }
   if (i % 19) printf("\n");

   return T;
}

node *lrot ( node *T )
{
   node *R, *RL;

   if ((T == NULL) || (T -> right == NULL)) return T;
   R = T -> right; RL = R -> left;
   T -> right = RL; R -> left = T;
   return R;
}

node *rrot ( node *T )
{
   node *L, *LR;

   if ((T == NULL) || (T -> left == NULL)) return T;
   L = T -> left; LR = L -> right;
   T -> left = LR; L -> right = T;
   return L;
}

node *tree2list ( node *T )
{
   node *p;

   p = T;
   while (p -> left) {
      while (p -> left -> right != NULL) p -> left = lrot(p -> left);
      p = p -> left;
   }

   p = T;
   while (p -> right) {
      while (p -> right -> left != NULL) p -> right = rrot(p -> right);
      p = p -> right;
   }

   printf("\n+++ Flattened tree\n"); printtree(T,0);

   p = T;
   while (p -> right) {
      p -> right -> left = p;
      p = p -> right;
   }

   p = T;
   while (p -> left) {
      p -> left -> right = p;
      p = p -> left;
   }
   return p;
}

node *list2tree ( node *L )
{
   node *T, *U;

   if (L == NULL) return NULL;
   T = L; U = L -> right;
   while (U) {
      T = T -> right;
      U = U -> right;
      if (U) U = U -> right;
   }
   if (T -> left) {
      T -> left -> right = NULL;
      T -> left = list2tree(L);
   }
   if (T -> right) {
      T -> right -> left = NULL;
      T -> right = list2tree(T -> right);
   }
   return T;
}

int main ( int argc, char *argv[] )
{
   int n;
   node *T, *L;

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

   T = genBST(n);
   printf("\n+++ Initial tree\n"); printtree(T,0);

   L = tree2list(T);
   printf("\n+++ Linked list\n"); printlist(L);

   T = list2tree(L);
   printf("\n+++ Balanced tree\n"); printtree(T,0);

   exit(0);
}