/*! A simple binary tree implementation. */

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

/* A type that defines a node in a binary tree */
typedef struct node {
  struct node * right;          /* right child */
  struct node * left;           /* left child */
  int value;                    /* data (chosen to be int for simplicity */
} Node;

/* Function pointer */
typedef void(Op)(void *);

/*! Allocates a new node and initialize it */
Node *create_node(int value)
{
  Node * tmp = (Node *) malloc(sizeof(Node));
  if (!tmp) {
    fprintf(stderr, "ERROR: not enough memory!\n");
    return NULL;
  }
  tmp->left = tmp->right = NULL;
  tmp->value = value;
  return tmp;
}

/* Inserts a given value into a tree pointed by root */
Node * insert(Node * root, int value)
{
  Node * parent;
  Node * child;
  Node * new_node;

  new_node = create_node(value);
  if (!new_node) return NULL;
  if (!root) return new_node;
  child = root;
  while (child) {
    parent = child;
    if (child->value > value)
      child = child->left;
    else
      child = child->right;
  }
  if (parent->value > value)
    parent->left = new_node;
  else
    parent->right = new_node;
  return root;
}

/*! Prints the tree pointed by root in ascending order */
void print_tree(Node * root)
{
  if (!root) return;
  print_tree(root->left);
  printf("%d ", root->value);
  print_tree(root->right);
}

/*! Deallocates all memory allocated for the tree pointed by root */
void clean_tree(Node * root)
{
  if (!root) return;
  clean_tree(root->left);
  clean_tree(root->right);
  free(root);
}

/* Traverses the tree in left, middle, then right order */
void traverse_tree(Node * root, Op * op)
{
  if (!root) return;
  traverse_tree(root->left, op);
  op((void *)root->value);
  traverse_tree(root->right, op);
}

/* Prints the value of a node */
void print_node(void * value)
{
  printf("%d ", (int) value);
}

/*! MAIN */
int main(int argc, char * argv[])
{
  Node *root = create_node(5);
  if (!root) return -1;
  if (!insert(root, 8)) return -1;
  if (!insert(root, 3)) return -1;
  if (!insert(root, 10)) return -1;
  if (!insert(root,2)) return -1;

  /* Method 1: */
  print_tree(root);
  printf("\n");
  
  /* Method 2: */
  traverse_tree(root, print_node);
  printf("\n");
  
  clean_tree(root);
  return 0;
}