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

struct bst {
   int value;
   struct bst* left;
   struct bst* right;
};

void bst_add2(struct bst*, struct bst*);
void bst_add(struct bst** tree, int value);
int bst_search(struct bst* tree, int value);
int bst_getCount(struct bst* tree);
int bst_getDepth(struct bst* tree);
int bst_getMin(struct bst* tree);
int bst_getMax(struct bst* tree);
void bst_print(struct bst* tree);
void command_search(struct bst* tree);
void command_add(struct bst** tree);
void command_print(struct bst* tree);
void question2(void);
void question3(void);
void question4(void);

void bst_add2(struct bst* tree, struct bst* n) {
   if (n->value < tree->value) {
      if (tree->left == NULL) {
         tree->left = n;
      } else {
         bst_add2(tree->left, n);
      }
   } else {
      if (tree->right == NULL) {
         tree->right = n;
      } else {
         bst_add2(tree->right, n);
      }
   }
}

void bst_add(struct bst** tree, int value) {
   struct bst* n;
   
   n = malloc(sizeof(struct bst));
   n->value = value;
   n->left = NULL;
   n->right = NULL;
   
   if (*tree == NULL) {
      *tree = n;
   } else {
      bst_add2(*tree, n);
   }
}

int bst_search(struct bst* tree, int value) {
   if (tree == NULL) {
      return 0;
   }
   if (value < tree->value) {
      return bst_search(tree->left, value);
   } else if (tree->value < value) {
      return bst_search(tree->right, value);
   } else {
      return 1;
   }
}

int bst_getCount(struct bst* tree) {
   if (tree == NULL) {
      return 0;
   } else {
      return bst_getCount(tree->left) + bst_getCount(tree->right) + 1;
   }
}

int bst_getDepth(struct bst* tree) {
   int l;
   int r;
   if (tree == NULL) {
      return 0;
   } else {
      l = bst_getDepth(tree->left);
      r = bst_getDepth(tree->right);
      if (l < r) {
         return r + 1;
      } else {
         return l + 1;
      }
   }
}

int bst_getMin(struct bst* tree) {
   if (tree == NULL) {
      return -1;
   } else {
      if (tree->left == NULL) {
         return tree->value;
      } else {
         return bst_getMin(tree->left);
      }
   }
}

int bst_getMax(struct bst* tree) {
   if (tree == NULL) {
      return -1;
   } else {
      if (tree->right == NULL) {
         return tree->value;
      } else {
         return bst_getMax(tree->right);
      }
   }
}

void bst_print(struct bst* tree) {
   if (tree == NULL) {
      return;
   }
   bst_print(tree->left);
   printf("%d\n", tree->value);
   bst_print(tree->right);
}

void command_search(struct bst* tree) {
   int n;
   printf("search\n");
   printf("data>");
   scanf("%d%*c", &n);
   if (bst_search(tree, n)) {
      printf("data already exists\n");
   } else {
      printf("data does not exist\n");
   }
}

void command_add(struct bst** tree) {
   int n;
   printf("add\n");
   printf("data>");
   scanf("%d%*c", &n);
   printf("n:%d\n", n);
   bst_add(tree, n);
}

void command_print(struct bst* tree) {
   printf("print\n");
   bst_print(tree);
}

void question2(void) {
   struct bst* tree;
   tree = NULL;
   bst_add(&tree, 6);
   bst_add(&tree, 4);
   bst_add(&tree, 3);
   bst_add(&tree, 8);
   bst_add(&tree, 5);
   bst_add(&tree, 9);
   bst_add(&tree, 7);
   bst_print(tree);
}

void question3(void) {
   struct bst* tree;
   char c;
   tree = NULL;
   while (1) {
      printf("s:search, i:add, p:print, q:quit\n");
      printf("command>");
      scanf("%c%*c", &c);
      if (c == 's') {
         command_search(tree);
      } else if (c == 'i') {
         command_add(&tree);
      } else if (c == 'p') {
         command_print(tree);
      } else if (c == 'q') {
         break;
      }
   }
}

void question4(void) {
   struct bst* tree;
   int i;
   tree = NULL;
   for (i = 0; i < 10000; i++) {
      bst_add(&tree, rand() % 10000);
   }
   printf("データの総数 %d\n", bst_getCount(tree));
   printf("木の深さの最大値 %d\n", bst_getDepth(tree));   
   printf("データの最小値 %d\n", bst_getMin(tree));   
   printf("データの最大値 %d\n", bst_getMax(tree));
}

int main(void) {
   question2();
   question3();
   question4();
   return EXIT_SUCCESS;
}