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

typedef struct node {
  int value;
  struct node *left;
  struct node *right;
} Node;

Node *
newNode(int n){
  Node *obj;
  obj = (Node *)malloc(sizeof(Node));
  obj->value = n;
  obj->left = NULL;
  obj->right = NULL;
  return obj;
}

Node *
addNode(Node *obj, int n){
  if(obj == NULL){
    return newNode(n);
  }

  if(obj->value == n){
    /*do nothing*/
  }else if(obj->value < n){
    obj->right = addNode(obj->right, n);
  } else{
    obj->left = addNode(obj->left, n);/*   (6)   */
  }

  return obj;
}


Node *
appendRightEnd(Node *obj, Node *right){
  if(obj != NULL){
    if(obj->right == NULL){
      obj->right = right;
    }else{
      obj->right = appendRightEnd(obj->right, right);/*   (7)   */;
    }
  }
  return obj;
}


Node *
deleteNode(Node *obj, int n){
  Node *newobj;

  if(obj != NULL){
    if(obj->value == n){

      if (obj->left == NULL){
	newobj = obj->right;
	free(obj);
	return newobj;
      }else if(obj->right == NULL){
	newobj = obj->left;/*   (8)   */
	free(obj);
	return newobj;
      }else{

	obj->left = appendRightEnd(obj->left, obj->right);
	newobj = obj->left;
	free(obj);
	return newobj;
      }
    }else{
      if(obj->value < n)
	obj->right = deleteNode(obj->right, n);
      else
	obj->left = deleteNode(obj->left, n);/*   (9)   */
    }
  }
  return obj;
}


void
printNodes(Node *obj){
  if(obj != NULL){
    if(obj->left != NULL){
      printNodes(obj->left);
    }

    printf("%d\t", obj->value);

    if(obj->right != NULL){
      printNodes(obj->right);
    }
  }

}

int
main(int argc, char *argv[]){
  Node *topnode = NULL;

  topnode = addNode(topnode, 5);
  topnode = addNode(topnode, 7);
  topnode = addNode(topnode, 1);
  topnode = addNode(topnode, -1);
  topnode = addNode(topnode, 4);
  topnode = addNode(topnode, 10);

  printNodes(topnode);
  printf("\n");
  topnode = deleteNode(topnode, 5);

  printNodes(topnode);
  printf("\n");
}