#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;
};

typedef struct StackNode* StackNode;
struct StackNode {
   void* value;
   StackNode next;
};

typedef struct Stack* Stack;
struct Stack {
   StackNode root;
};

typedef struct DumpState* DumpState;
struct DumpState {
   int state;
   Node node;
   int indent;
};

void Stack_push(Stack stack, void* value) {
   StackNode node = malloc(sizeof(struct StackNode));
   node->value = value;
   node->next = stack->root;
   stack->root = node;
}

void* Stack_pop(Stack stack) {
   void* value;
   StackNode node;
   if (stack->root == NULL) {
      return NULL;
   } else {
      node = stack->root;
      stack->root = node->next;
      value = node->value;
      free(node);
      return value;
   }
}

void Tree_add(Tree tree, int value) {
   Node n;
   Node p;
   
   n = malloc(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 Tree_dump(Tree tree) {
   Stack stack;
   DumpState ds;
   DumpState ds2;
   const int right = 0;
   const int left = 1;
   int state;
   Node node;
   int indent;
   int indent2;
   int i;
   
   if (tree->root == NULL) {
      return;
   }
   stack = malloc(sizeof(struct Stack));
   ds = malloc(sizeof(struct DumpState));
   ds->state = right;
   ds->node = tree->root;
   ds->indent = 0;
   Stack_push(stack, ds);
   while (stack->root != NULL) {
      ds = Stack_pop(stack);
      state = ds->state;
      node = ds->node;
      indent = ds->indent;
      if (state == right) {
         indent2 = indent;
         do {
            ds2 = malloc(sizeof(struct DumpState));
            ds2->state = left;
            ds2->node = node;
            ds2->indent = indent2;
            Stack_push(stack, ds2);
            indent2 = indent2 + 1;
            node = node->right;
         } while (node != NULL);
      } else if (state == left) {
         for (i = 0; i < indent; i++) {
            printf("　");
         }
         printf("%d\n", node->value);
         if (node->left != NULL) {
            ds2 = malloc(sizeof(struct DumpState));
            ds2->state = right;
            ds2->node = node->left;
            ds2->indent = indent + 1;
            Stack_push(stack, ds2);            
         }
      }
      free(ds);
   }
   free(stack);
}

int main(void) {
   Tree tree = malloc(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);
   return EXIT_SUCCESS;
}