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

typedef struct tr
{
  int* data;
  struct tr *left, *right;
}
btree, *btreeptr;


int key(const int * item)
{
  return *item;
}

btreeptr insert(int* item, btreeptr b)
{
  btreeptr n;
  if (NULL == b)
  {
    n = (btreeptr)malloc(sizeof(btree));
    n->data = item;
    n->left = NULL;
    n->right = NULL;
    return n;
  }

  if (key(item) < key(b->data))
  {
    b->left = insert(item, b->left);
  }

  if (key(item) > key(b->data))
  {
    b->right = insert(item, b->right);
  }

  return b;
}

int * getmem(const int number)
{
  int *n;

  n = (int*)malloc(sizeof(int));
  *n = number;
  return n;
}

void visit(int* item)
{
  printf("%d ", *item);
}

void inorder(btreeptr b)
{
  if (NULL == b) return;

  inorder(b->left);
  visit(b->data);
  inorder(b->right);
}

int max (const int a, const int b)
{
  return (a>b)?a:b;
}

int height(btreeptr b)
{
  if (NULL == b)
    return 0;

  return max(height(b->left), height(b->right))+1;
}

int size(btreeptr b)
{
  if (NULL == b)
    return 0;

  return size(b->left) +size(b->right)+1;
}

int numberOfLeaves(btreeptr b)
{
  if (NULL == b)
    return 0;

  if (NULL == b->left && NULL == b->right)
    return 1;

  return numberOfLeaves(b->left) +numberOfLeaves(b->right);
}


int main(void) {
  btreeptr rootptr = NULL;

  printf("Füge Zahlen in folgender Reihenfolge ein: 1, 3, 2, 8, 5, 4, 9.\n");
  rootptr = insert(getmem(1), rootptr);
  insert(getmem(3), rootptr);
  insert(getmem(2), rootptr);
  insert(getmem(8), rootptr);
  insert(getmem(5), rootptr);
  insert(getmem(4), rootptr);
  insert(getmem(9), rootptr);

  printf("Inorder-Durchlauf zur Kontrolle:\n");
  inorder(rootptr);
  printf("\n");
  printf("Höhe des Baumes: %d\n", height(rootptr));
  printf("Anzahl der Knoten: %d\n", size(rootptr));
  printf("Anzahl der Blätter: %d\n", numberOfLeaves(rootptr));

  return 0;
}