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

/* #define DEBUG */
#if defined(DEBUG)
#include "xmalloc.h"
#else
#define xmalloc(x, y) malloc(x)
#define xfree(x, y) free(x)
#define xrealloc(x, y, z) realloc(x, y)
#define xmallocdump()
#endif

#define ID_TREE      1001
#define ID_NODE      1002

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

void Node_init(Node node, int value) {
  node->value = value;
  node->left = node->right = 0;
}

Node Node_add(Node root, int value) {
  if (root == 0) {
    Node n;
    if ((n = xmalloc(sizeof(struct _Node), ID_NODE)) != 0) {
      Node_init(n, value);
      return n;
    } else {
      return 0;
    }
  /* changed to recursive!! */
  } else if (value < root->value) {
    root->left = Node_add(root->left, value);
  } else {
    root->right = Node_add(root->right, value);
  }
  return root;
}

void Node_release(Node root) {
  if (root == 0)
    return;
  Node_release(root->left);
  Node_release(root->right);
  xfree(root, ID_NODE);
  root = 0; /* not necessary */
}

/* ------------------------------------- */
typedef struct _Tree {
   struct _Node *root;
} *Tree;
 
void Tree_init(Tree tree) {
  tree->root = 0;
}

void Tree_add(Tree tree, int value) {
  tree->root = Node_add(tree->root, value);
}

void Tree_release(Tree tree) {
  if (tree) {
    Node_release(tree->root);
    tree->root = 0; /* to be necessary or not to be? */
  }
}

void Tree_dump_local(Node node, int level) {
  int i;
  if (node->right)
    Tree_dump_local(node->right, level + 1);
  for (i = 0; i < level; i++) {
    putchar(' ');
    putchar(' ');  
  }
  printf("%d\n", node->value);
  if (node->left)
    Tree_dump_local(node->left, level + 1);
}

void Tree_dump(Tree tree) {
  Tree_dump_local(tree->root, 0);
}
 
/* ------------------------------------- */
int main() {
  Tree tree;
  if ((tree = xmalloc(sizeof(struct _Tree), ID_TREE)) != 0) {
    Tree_init(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);

    Tree_release(tree);
    xfree(tree, ID_TREE);
  }
  xmallocdump();
  return 0;
}
/* end */