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

struct btree_struct {
  int key, data;
  struct btree_struct *left, *right;
  };

typedef struct btree_struct btree;

int getData(int k, btree *node, int *d);
int insert(int k, int d, btree **node);
int delete(int k, btree **node);

int main(){
  btree *root = NULL;
  int n, ok;

  /* fill tree with some sample values */
  ok = insert(14, 1400, &root);
  printf(" 14 added: %d\n", ok);
  ok = insert(1, 100, &root);
  printf(" 1  added: %d\n", ok);
  ok = insert(20, 2000, &root);
  printf(" 20 added: %d\n", ok);
  ok = insert(5, 500, &root);
  printf(" 5  added: %d\n", ok);
  ok = insert(0, 0, &root);
  printf(" 0  added: %d\n", ok);

  /* test getData() */
  ok = getData(1, root, &n);
  printf(" 1  is member: %d, value: %d\n", ok, n);
  ok = getData(14, root, &n);
  printf(" 14 is member: %d, value: %d\n", ok, n);
  ok = getData(3, root, &n);
  printf(" 3  is member: %d\n", ok);

  /* test deletion */
  ok = delete(1, &root);
  printf(" Element 1 deleted: %d\n", ok);
  ok = getData(1, root, &n);
  printf(" 1 is member: %d\n", ok);

  return 0;
}


/*
 * Checks whether a given key k occurs in the tree starting at node, and
 * returns the respective data element.
 * Parameters:
 *  k: key to search for
 *  node: of tree to be checked
 *  d: pointer to an integer, filled with data if k found
 * Returns: 1 if the respective key was found, 0 otherwise
 */ 
int getData(int k, btree *node, int *d){
  if (node == NULL) { /* not found */
    d = NULL; 
    return 0;
    }
  else if (node->key == k) { /* key found */
    *d = node->data;
    return 1;
    }
  else if (node->key < k) /* if key occurs, it must be in right subtree */
    return getData(k, node-> right, d);
  else /* if key occurs, it must be in left subtree */
    return getData(k, node-> left, d);
}

/*
 * Inserts the pair (k, d) into the tree starting at node.
 * Parameters:
 *  k: key to be inserted
 *  d: respective data
 *  node: root of the subtree where the element should be added
 * Returns: 0 if an element with this key already exists, and the new
 *          element was not added; 1 otherwise.
 */
int insert(int k, int d, btree **node) {
  btree *n = *node, *newnode = NULL, *parent = NULL;

  /* create new node */
  newnode = (btree*) malloc(sizeof(btree));
  newnode->key = k;
  newnode->data = d;

  /* search for place to insert */
  while (n != NULL) {
    if (n->key == k) /* key already exists -> fail */
      return 0;
    else { 
      parent = n;
      if (n->key < k)
        n = n->right;
      else
        n = n->left; 
      }
  }
  if (parent == NULL) /* insert at root */
    *node = newnode;
  else /* attach as child node */
  if (parent->key < k)
    parent->right = newnode;
  else
    parent->left = newnode;
  return 1;
}

/*
 * Deletes the key k in the tree starting at node.
 * Parameters:
 *  k: key to be inserted
 *  node: root of the subtree where the element should be added
 * Returns: 0 if the key was  not found; 1 otherwise.
 *          The subtree of node is altered such that k is removed.
 */
int delete(int k, btree **node) {
  btree *n = *node, *parent = NULL;

  /* search for key in tree */
  while ((n != NULL) && (n->key != k)) {
    parent = n;
    if (k < n->key)
      n = n->left;
    else
      n = n->right; 
    }

  /* if key was not found, fail */
  if (n == NULL) 
    return 0;

  /* otherwise, n is the node to be deleted */
  /* special case 0: delete root in a single-node tree */
  if (parent == NULL)
    *node = NULL;
  /* easy case 1: no left child */
  else if (n->left == NULL)
    if (k <= parent->key)
      parent->left = n->right;
    else
      parent->right = n->right;
  /* easy case 2: no right child */
  else if (n->right == NULL)
    if (k <= parent->key)
      parent->left = n->left;
    else
      parent->right = n->left;
  /* case 3: n is inner node */
  else {
    /* search predecessor node pred */
    btree *pred = n->left;
    btree *pred_parent = n;
    while (pred->right != NULL){
      pred_parent = pred;
      pred = pred->right;
    }
    /* pred is direct predecessor of n in tree */
    pred_parent->right = NULL; /* delete pred at original place */
    /* copy pred key and data to n */
    n->key = pred->key;
    n->data = pred->data;
  } 
  return 1;   
}