struct Node
{
  item data;
  struct Node* left;
  struct Node* right;
};

struct Node* tree_insert(struct Node* root, item key)
{  
  if( root == NULL) /* INSERTING A ROOT NODE */
    {
      root = (struct Node*) malloc( sizeof(struct Node));
      root->data = key;
      root->left = NULL;
      root->right = NULL;
    }
  else /* INSERTING A NON-ROOT NODE */
    {
      if(root->data > key)
	root->left = tree_insert(root->left, key);
      else
	root->right = tree_insert(root->right, key);
    }

  return root;
}

/* ======================================================= */

struct Node* tree_delete(struct Node* root, struct Node* target)
{
  struct Node* victim = (struct Node*)NULL;
  struct Node* child = (struct Node*)NULL;

  if(root == NULL || target == NULL)
    return root;

  /* 
   * victim is the target node, if target is a leaf
   * node or only has one child; Or, victim is the successor
   * of z, if z has two children.
   */

  if(target->left == NULL || target->right == NULL)
    victim = target;
  else
    victim = tree_successor(root, target);
    
  /*
   * chlid is set to the non-NULL child of y, or NULL, if y 
   * has no children. By default, left child is more preferable
   * than right, if y has two children.
   */
  if(victim->left != NULL)
    child = victim->left;   
  else if(victim->right != NULL)
    child = victim->right; 
  else
    child = (struct Node*)NULL;    

  if(tree_parent(root, victim) == NULL) // victim is the ROOT
    root = child;   
  else if( (tree_parent(root, victim)->right != NULL) && (victim == tree_parent(root, victim)->right) )
    tree_parent(root, victim)->right = child;    
  else if( (tree_parent(root, victim)->left != NULL) && ( victim == tree_parent(root, victim)->left ) )
    tree_parent(root, victim)->left = child;	    
  else
    printf("Wrong!! You shouldn't be here!!\n");  

  if(victim != target)
    target->data = victim->data;
  
  free(victim);
  child = (struct Node*) NULL;
      
  return root;
}

/* ======================================================= */

void tree_inorder_traversal(struct Node* root) /* in-order traversal */
{
  if(root != NULL) 
    {
      tree_inorder_traversal(root->left);
      printf("[%d]->", root->data);
      tree_inorder_traversal(root->right);
    }

  return;
}

/* ======================================================= */

void tree_preorder_traversal(struct Node* root) /* pre-order traversal */
{
  if(root != NULL)
    {
      printf("[%d]->", root -> data);
      tree_preorder_traversal(root -> left);
      tree_preorder_traversal(root -> right);
    }

  return;
}

/* ======================================================= */

void tree_postorder_traversal(struct Node* root) /* post-order traversal */
{
  if(root != NULL)
    {
      tree_postorder_traversal(root->left);
      tree_postorder_traversal(root->right);
      printf("[%d]->", root->data);
    }

  return;
}

/* ======================================================= */

struct Node* tree_search(struct Node* root, item key) /* Binary Search */
{
  if( root == NULL)
    return (struct Node*) NULL;
  else if(root -> data == key)
    return root;
  else if(root->data > key)
    return tree_search(root->left, key);
  else if(root->data < key)
    return tree_search(root->right, key);
}

/* ======================================================= */

struct Node* tree_min(struct Node* root)
{
  if(root != NULL )
    for(; root->left != NULL; root = root -> left);
  return root;
}

/* ======================================================= */

struct Node* tree_max(struct Node* root)
{
  if(root != NULL)
    for(; root->right != NULL; root = root -> right);
  return root;
}

/* ======================================================= */

struct Node* tree_successor(struct Node* root, struct Node* target)
{
  if(root == NULL || target == NULL)
    return (struct Node*) NULL;
  else if(target->right == NULL)
    {
      struct Node* cursor = tree_parent(root, target);
      while( (cursor != NULL) && (target->data >= cursor->data))
	{
	  target = cursor;
	  cursor = tree_parent(root, target);
	}
      return cursor;
    }
  else
    return tree_min(target->right);

}

/* ======================================================= */

struct Node* tree_predecessor(struct Node* root, struct Node* target)
{
  if(root == NULL || target == NULL)
    return (struct Node*) NULL;
  else if(target->left == NULL)
    {
      struct Node* cursor = tree_parent(root, target);
      while( (cursor != NULL) && (target->data < cursor->data))
	{
	  target = cursor;
	  cursor = tree_parent(root, target);
	}
      return cursor;
    }
  else
    return tree_max(target->left);
}

/* ======================================================= */

size_t tree_height(struct Node* root)
{
  if(root == NULL)
    return 0;
  else if( (root->right == NULL) && (root->left == NULL) )
    return 0;
  else if( tree_height(root->left) > tree_height(root->right) )
    return 1 + tree_height(root->left);
  else
    return 1 + tree_height(root->right);
}
/* ======================================================= */

size_t tree_depth(struct Node* root, struct Node* target)
{
  if(target == NULL)
    return -1;
  else if(root == target)
    return 0;
  else
    return 1 + tree_depth(root, tree_parent(root, target));
}