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

#ifndef _Tree_H

typedef struct searchTreeNode *tree;
typedef *searchTree *position;

struct serachTreeNode
{
   ElementType element;
   ptr left;
   ptr right;
       };
      
tree MakeEmpty(tree);
position Find(ElementType,tree);
position FindMin(tree);
position FindMax(tree);
tree Insert(ElementType,tree);
ElementType Retrieve(position);
tree Delete(ElementType,tree);

#endif

tree MakeEmpty(tree t)
{
   if(t!=NULL)
   {
     MakeEmpty(t->left);
     MakeEmpty(t->right);
     free(t);
   }
     return NULL;
}

tree Find(ElementType x,tree t)
{
   if(t!=NULL)
   {
      if(compare(x,p->element)==-1)
         return Find(x,t->left);
      else
         if(compare(x,p->element)==1)
            return Find(x,t->right);
         else
             return t;
   }
   else
       return NULL;
}

tree FindMin(tree t)
{
   if(t!=NULL)
   {
     while(t->left!=NULL)
          t=t->left;
     return t;
   }
   else
      return NULL;
}

tree FindMax(tree t)
{
   if(t!=NULL)
   {
      if(t->left!=NULL)
         return FindMax(t->right);   
   }
   else
      return NULL;
}

tree Insert(Element x,tree t)
{
   if(t==NULL)
   {
      tree tmp=(tree)malloc(sizeof(struct searchTree));
      tmp->element=x;
      tmp->left=tmp->right=NUll;
   }
   else
   {
      if(compare(x,t)==-1)
         t->left=Insert(x,t->left);
      if(compare(x,t)==1)
         t->right=Insert(x,t->right);
   }
   return t;    
}

ElementType Retrieve(position p)
{
  return p->Element;
}