#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){
  Node *iobj;

  if(obj == NULL){
    return newNode(n);
  }
  iobj = obj;

  while(1){
    if(iobj->value == n){
      break;
    }else if(iobj->value < n){
      if(iobj->right == NULL){
	iobj->right = newNode(n);
	break;
      }else{
	iobj = iobj->right;
      }
    }else{
      if( iobj->left == NULL){
	iobj->left = newNode(n);
	break;
      }else{
	iobj = iobj->left;
      }
    }
  }
  return obj;
}


Node *
deleteThisNode(Node *obj){
  Node *tmpobj;
  Node *iobj;

  if(obj == NULL) return NULL;
  if(obj->left == NULL){
    tmpobj = obj->right;
    free(obj);
  }else if(obj->right == NULL){
    tmpobj = obj->left;
    free(obj);
  }else{

    tmpobj = obj->left;

    iobj = tmpobj;
    while(iobj->right != NULL){
      iobj = iobj->right;
    }
    iobj->right = obj->right;
    free(obj);
  }
  return tmpobj;
}


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

  if(obj->value == n){
    obj = deleteThisNode(obj);
    return obj;
  }else{

    pobj = obj;
    while(1){
      if(pobj->value < n){
	if(pobj->right == NULL){
	  break;
	}else{
	  if(pobj->right->value==n){
	    pobj->right = deleteThisNode(pobj->right);
	    break;
	  }else{
	    pobj = pobj->right;
	  }
	}
      }else{

	if(pobj->left == NULL){
	  break;
	}else{
	  if(pobj->left->value == n){
	    pobj->left = deleteThisNode(pobj->left);
	    break;
	  }else{
	    pobj = pobj->left;
	  }
	}
      }
    }
  }
}


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");
}