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

typedef struct Node* Node;
struct Node {
   int value;
   Node left;
   Node right;
};

typedef struct Tree* Tree;
struct Tree {
   Node root;
};

void Tree_add(Tree tree, int value) {
   Node n;
   Node p;
   
   n = calloc(1,sizeof(struct Node));
   n->value = value;
   n->left = NULL;
   n->right = NULL;
   
   if (tree->root == NULL) {
      tree->root = n;
   } else {
      p = tree->root;
      while (1) {
         if (value < p->value) {
            if (p->left == NULL) {
               p->left = n;
               break;
            } else {
               p = p->left;
            }
         } else {
            if (p->right == NULL) {
               p->right = n;
               break;
            } else {
               p = p->right;
            }
         }
      }
   }
}

void print_node(Node n,size_t depth){
    while(depth--){
        putchar(' ');
    }
    printf("%d\n",n->value);
}

void dump_tree_impl(Node n,size_t depth){
    if(n){
        dump_tree_impl(n->right,depth + 1);
        print_node(n,depth);
        dump_tree_impl(n->left,depth + 1);
    }
}

void free_node(Node n){
    if(n){
        free_node(n->right);
        free_node(n->left);
        free(n);
    }
}

void free_tree(Tree t){
    free_node(t->root);
    free(t);
}

void Tree_dump(Tree tree) {
    dump_tree_impl(tree->root,0);
}

int main(void) {
   Tree tree = calloc(1,sizeof(struct Tree));
   Tree_add(tree, 3);
   Tree_add(tree, 1);
   Tree_add(tree, 5);
   Tree_add(tree, 0);
   Tree_add(tree, 2);
   Tree_add(tree, 4);
   Tree_add(tree, 6);
   Tree_dump(tree);
   free_tree(tree);
   return EXIT_SUCCESS;
}