Hi,

I am working on a C implementation of a BST. Every function I've written so far appears to work. I have the following structure for BST nodes:

Code:
typedef struct node {
  Employee *element;
  struct node *left, *right;
} NODE;
Where Employee is the following structure:

Code:
typedef struct {
  char name[30];
  long ID;
  char address[40];
  char city[20];
  int age;
} Employee;
So far, this is what my implementation looks like:

Code:
/* for file i/o and debugging */
#include <stdio.h>
/* for assert() */
#include <assert.h>
/* for memory allocation */
#include <stdlib.h>


/* print a tree */
void printInOrder(FILE *fpout, NODE *root, int depth) {
  /* if the node is empty, do nothing */
  if (root == NULL || (root != NULL && root->element == NULL)) return;
  
  /* print left subtree */
  printInOrder(fpout, root->left, depth + 1);


  /* print node */
  int i;
  for (i = 0; i < depth; i++) fprintf(fpout, " ");
  fprintf(fpout, "[%ld] [%s] [%s]\n", root->element->ID, root->element->name, root->element->address);
  
  /* print right subtree */
  printInOrder(fpout, root->right, depth + 1);
}


/* compare two employees */
static boolean empcmp(Employee emp1, Employee emp2) {
  return emp1.ID > emp2.ID;
}


static NODE *minNode(NODE *root) {
  NODE *node = root;
  while (node->left != NULL) node = node->left;
  return node;
}


/* delete a node */
static void deleteNode(NODE **node) {
  /* if this node is a leaf node */
  if ((*node)->left == NULL && (*node)->right == NULL) {
    free((*node)->element);
    free(*node);
  }


  /* if this node has 1 left child */
  else if ((*node)->left != NULL && (*node)->right == NULL) {
    NODE *old_root = *node;
    *node = (*node)->left;
    free(old_root->element);
    free(old_root);
  }


  /* if this node has 1 right child */
  else if ((*node)->right != NULL && (*node)->left == NULL) {
    NODE *old_root = *node;
    *node = (*node)->right;
    free(old_root->element);
    free(old_root);
  }


  /* if this node has both children */
  else {
    NODE *successor = minNode((*node)->right);
    *((*node)->element) = *(successor->element);
    free(successor->element);
    free(successor);
  }
}


/* return the maximum of two integers */
static int max(int num1, int num2) {
  return (num1 > num2 ? num1 : num2);
}


/* compare two nodes */
static boolean nodecmp(NODE *node1, NODE *node2) {
  /* if node1 has an employee element associated with it */
  if (node1->element != NULL) {
    if (node2->element != NULL) return empcmp(*(node1->element), *(node2->element));
    else return TRUE;
  }


  /* otherwise, return false */
  else return FALSE;
}


/* initialize a new binary search tree. */
void initialize(NODE **root) {
  *root = (NODE *) malloc(sizeof(NODE));
  (*root)->left = (*root)->right = NULL;
}


/* insert a new employee at the tree rooted at `root`. */
boolean insert(NODE **root, Employee e) {
  /* create the node to be added to the tree */
  NODE *new_node = (NODE *) malloc(sizeof(NODE));
  assert(new_node != NULL);


  new_node->right = new_node->left = NULL;


  /* create the employee pointer */
  new_node->element = (Employee *) malloc(sizeof(Employee));
  assert(new_node != NULL);
  
  /* copy over the employee record to the node */
  *(new_node->element) = e;


  /* if this tree is empty */
  if (*root == NULL || (*root != NULL && (*root)->element == NULL)) {
    *root = new_node;
    return TRUE;
  }


  /* if *root > new_node */
  else if (nodecmp(*root, new_node)) {
    free(new_node->element);
    free(new_node);
    /* insert into left subtree of root */
    return insert(&((*root)->left), e);
  }


  /* if new_node > *root */
  else if (nodecmp(new_node, *root)) {
    free(new_node->element);
    free(new_node);
    /* insert into right subtree */
    return insert(&((*root)->right), e);
  }


  /* node already exists in the tree */
  else return FALSE;
}


boolean delete(NODE **root, long id, Employee *result) {
  if (*root == NULL) return FALSE;


  if ((*root)->element->ID == id) {
    *result = *((*root)->element);
    deleteNode(root);
    return TRUE;
  }
  
  else if ((*root)->left && (*root)->left->element->ID == id) {
    *result = *((*root)->element);
    deleteNode(&((*root)->left));
    (*root)->left = NULL;
    return TRUE;
  }


  else if ((*root)->right && (*root)->right->element->ID == id) {
    NODE *old_left = (*root)->right->left;
    *result = *((*root)->right->element);
    deleteNode(&((*root)->right));
    return TRUE;
  }


  else if ((*root)->element->ID > id) return delete(&((*root)->left), id, result);


  else return delete(&((*root)->right), id, result);
}


boolean search(NODE *root, long id, int *comp, Employee *result) {
  /* bump the number of three-way comps done */
  (*comp)++;
  
  /* if the tree is empty, we were unable to find the matching ID. */
  if (root == NULL) return FALSE;
  
  /* search the left subtree */
  else if (root->element->ID > id) return search(root->left, id, comp, result);
  
  /* search the right subtree */
  else if (root->element->ID < id) return search(root->right, id, comp, result);
  
  /* found it! */
  else {
    *result = *(root->element);
    return TRUE;
  }
}


unsigned elementCount(NODE *root) {
  /* if this is an empty node, return 0 */
  if (root == NULL) return 0;


  /* otherwise, return the element count of the count of the two subtrees */
  else return 1 + elementCount(root->left) + elementCount(root->right);
}


int height(NODE *root) {
  /* if this is an empty node, return 0 */
  if (root == NULL) return 0;


  /* otherwise, return the hight of the maz of two subtrees */
  else return (1 + max(height(root->left), height(root->right)));
}
I'm having trouble with the delete() function, which works in the following situation: Whenever the node has two children, and the right child has no left child. However, delete() does not work in the following situation: Where the node has two children, and the right child DOES have a left child, the left child of that right child just disappears.

I understand why this happens, but I cannot quite figure out a way to solve the problem cleanly. I am open to any suggestions. Thanks for reading such a long post!