#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MAXSIZE 10
typedef int elemtype;
typedef struct node {
  elemtype e;
  struct node * left;
  struct node * right;
} Node;

typedef Node * LLP;

typedef struct tree {
  Node * root;
  int size;
} Tree;

typedef struct pair {
  Node * parent;
  Node * child;
} Pair;

typedef int ElemType;

typedef struct data {
    ElemType * elem;
    int length;
} Elem;

typedef struct stack {
    LLP data;
    struct stack * next;
} S;
typedef S * Stack;

void InitS(Stack * s)
{
    *s = NULL;
}

void Push(LLP e, Stack * s)
{
    Stack new = (Stack ) calloc (1,sizeof(S));
    if (!new)
    {
        fprintf(stderr,"failed to allocate memory for stack!\n");
        exit(1);
    }
    new->data = e;
    new->next = *s;
    *s = new;
}

void Pop(LLP * e, Stack * s)
{
    Stack p = *s;
    *e = (*s)->data;
    *s = (*s)->next;
    free(p);
}

void DestroyS(Stack * s)
{
    Stack p;

    if (*s)
    {
        p = *s;
        *s = (*s)->next;
        free(p);
    }
}

bool EmptyS(Stack * s)
{
    if (!*s)
        return true;
    return false;
}

void InitList(Elem * L)
{
    L->elem = (ElemType *) malloc (sizeof(ElemType) * MAXSIZE);

    if (!(L->elem))
    {
        fprintf(stderr,"Initialization Failed\nPlease run as debug mode\n");
        exit(EXIT_FAILURE);
    }

    L->length = 0;
}

void AddElem(Elem * L, Node * nd)	//recursive
{
    Stack p;
    InitS(&p);

    Node * n = nd;

    while (n || !EmptyS(&p))
    {
        if (n)
        {
             Push(n,&p);
             n = n->left;
        }
        else
        {
            Pop(&n,&p);
            L->elem[L->length++] = n->e;
            n = n->right;
        }
    }
    DestroyS(&p);
}

void DestroyList(Elem * L)
{
    if (L->elem)
        free(L->elem);
    else
        printf("Sequence list is not exist!\n");
}

int binarySearch(int e, Elem * L)
{
    int l = 0, r = L->length;
    int n;

    while (l < r)
    {
        n = (l+r)/2-1;
        if (L->elem[n] == e)
            return n;
        else if (L->elem[n] < e)
                l = n+1;
        else
                r = n;
    }
    return -1;
}

void InitTree(Tree * tr)
{
  tr->root = NULL;
  tr->size = 0;
}

static bool ToLeft(const elemtype e, const elemtype tree_e)
{
  return e < tree_e;
}

static bool ToRight(const elemtype e, const elemtype tree_e)
{
  return e > tree_e;
}

static Pair SeekItem(const elemtype e, Tree * ptr)
{
  Pair look = {NULL,ptr->root};
  
  while (look.child)
  {
    if (ToLeft(e,look.child->e))
    {
      look.parent = look.child;
      look.child = look.child->left;
    }
    else if (ToRight(e,look.child->e))
    {
      look.parent = look.child;
      look.child = look.child->right;
    }
    else
      break;
  }
  
  return look;
}

static bool AddNode(Node * new, Node * nd)
{
  if (ToLeft(new->e,nd->e))
  {
    if (nd->left == NULL)
      nd->left = new;
    else
      AddNode(new,nd->left);
  }
  else if (ToRight(new->e,nd->e))
  {
    if (nd->right == NULL)
      nd->right = new;
    else
      AddNode(new,nd->right);
  }
  else return false;
  return true;
}

void MidPrint(const Node * nd)	//recursive
{
  if (nd->left)
    MidPrint(nd->left);
  printf("  %d", nd->e);
  if (nd->right)
    MidPrint(nd->right);
}

bool AddItem(const elemtype e, Tree * ptr)
{
  Node * new;
  
  if (SeekItem(e, ptr).child)
    return false;
  
  new = (Node *) calloc (1,sizeof(Node));
  if (!new)
    return false;
  
  new->e = e;
  
  if (!ptr->root)
    ptr->root = new;
  else
    AddNode(new, ptr->root);
  return true;
}

bool ReleaseTree(Node * nd)
{
  Node * tmp = nd;
  if (tmp->right)
    ReleaseTree(tmp->right);
  if (tmp->left)
    ReleaseTree(tmp->left);
  free(tmp);
  return true;
}

int main(void)
{
  int num;
  Tree btree;
  Elem list;
  int position;
  InitTree(&btree);
  InitList(&list);
  
  for (int i = 0; i < 10; i++)
  {
    scanf("%d", &num);
    AddItem(num,&btree);
  }
  
  MidPrint(btree.root);	//recursive
  AddElem(&list, btree.root);
  putchar('\n');
  printf("%d\n",binarySearch(21,&list));
  
  ReleaseTree(btree.root);
  DestroyList(&list);
  
  return 0;
}