// bin_tree_recursive.c - binary tree, recursive solution

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

typedef struct _Node_ Node;

struct _Node_
{
  unsigned value;
  Node *greater;
  Node *smaller;
};

Node *newNode(unsigned value);
void deleteNode(Node *node);
unsigned getValueFromNode(Node *node);

struct _Tree_
{
  Node *root;
  unsigned depth;
};

typedef struct _Tree_ Tree;

Tree *newTree();
void deleteTree(Tree *tree);
void insertNodeInTree(Tree *tree,Node *node);
// for internal use only!
void insertNodeInSubtree(Node *sub_root,Node *node);
void showTree(Tree *tree);

void exitOnFatalErrorOutOfMemory();
void exitOnIllegalArgument(char *func_name);
void exitOnInternalError(char *func_name);

//------------------------------------------------------------
int main()
{
  unsigned input = 0;
  Node *node = NULL;
  Tree *my_tree = newTree();
  for(;;)
  {
    printf("Please enter a value (0 quits): ");
    scanf("%u",&input);
    if (!input)
      break;
    node = newNode(input);
    insertNodeInTree(my_tree,node);
  }
  return(0);
}

//------------------------------------------------------------
Node *newNode(unsigned value)
{
  Node *ret = (Node*)malloc(sizeof(Node));
  if (!ret)
    exitOnFatalErrorOutOfMemory();
  ret->value = value;
  ret->greater = ret->smaller = NULL;
  return(ret);
}

//------------------------------------------------------------
void deleteNode(Node *node)
{
      // not needed here, I leave this up to you
}

//------------------------------------------------------------
unsigned getValueFromNode(Node *node)
{
  if (!node)
    exitOnIllegalArgument("getValueFromNode");
  return(node->value);
}

//------------------------------------------------------------
Tree *newTree()
{
  Tree *ret = (Tree*)malloc(sizeof(Tree));
  if (!ret)
    exitOnFatalErrorOutOfMemory();
  ret->root = NULL;
  ret->depth = 0;
  return(ret);
}

//------------------------------------------------------------
void deleteTree(Tree *tree)
{
      // not needed here, I leave this up to you
}

//------------------------------------------------------------
void insertNodeInTree(Tree *tree,Node *node)
{
  if ((!tree) || (!node))
    exitOnIllegalArgument("insertNodeInTree");
  if (!tree->root)
  {
    tree->root = node;
    return;
  }
  insertNodeInSubtree(tree->root,node);
}

//------------------------------------------------------------
void insertNodeInSubtree(Node *sub_root,Node *node)
{
  if (!sub_root)
    exitOnInternalError("insertNodeInSubtree");
  if (node->value == sub_root->value) // already existing, ignore
    return;
  if (node->value > sub_root->value)
  {
    if (sub_root->greater)
      insertNodeInSubtree(sub_root->greater,node);
    else
      sub_root->greater = node;
    return;
  }
  if (sub_root->smaller)
    insertNodeInSubtree(sub_root->smaller,node);
  else
    sub_root->smaller = node;
}

//------------------------------------------------------------
// helper function if the program runs out of memory
void exitOnFatalErrorOutOfMemory()
{
  printf("Fatal Error: Out of Memory\n");
  exit(-1);
}

//------------------------------------------------------------
// helper function if an illegal argument occurs
void exitOnIllegalArgument(char *func_name)
{
  printf("Fatal Error: Illegal Argument in %s\n",func_name);
  exit(-2);
}

//------------------------------------------------------------
// helper function if an internal error occurs
void exitOnInternalError(char *func_name)
{
  printf("Fatal Error: Internal Error in %s\n",func_name);
  exit(-2);
}
