/*! A simple binary tree implementation. */
#include <stdlib.h>
#include <stdio.h>

#include "btree.h"

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

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

  new_node = create_node(data);
  if (!new_node) return NULL;
  if (!root) return new_node;
  child = root;
  while (child) {
    parent = child;
    child = (cmp(child->data, data) == 1) ? child->left : child->right;
  }
  if (cmp(parent->data, data) == 1)
    parent->left = new_node;
  else
    parent->right = new_node;
  return root;
}

/*! 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(root->data);
  traverse_tree(root->right, op);
}