Getting weird results in binary tree removal method

Question

I rewrote my binary tree implementation, and it's close, but the removal of subtrees is still lacking complete functionality.

Removing a tree with no children does not work at all. In fact, when calling a method to search the tree for instances of that removed tree, the search method returns true (even though that tree and the item contained within the tree are freed at the end of the removal method). I can't solve this one, even with gdb.

Removing a tree with one child works, even if it's the root node.

Removing a tree with two children only partially works. The left tree, a pointer, of the removed tree is set to be the pointer to that removed tree, a pointer which is held in the higher tree than the removed tree. However, the right of the removed tree is lost.

Tree.h

/*-------------------------------Tree.h---------------------------------*/ 

#ifndef TREE
#define TREE

#define MAXLEVEL 4
typedef struct cat{
    char *name; 
    int age; 
}Item;

/*User Comparison Function*/ 
typedef int (*comp)(const Item *, const Item *); 

typedef struct tree{
    int branches; 
    Item *item; 
    struct tree *left, *right; 
}Tree; 


Tree *initializeTree(Tree *); 
int isEmpty(Tree *); 
int isFull(Tree *); 
Tree **searchTree(Tree **, Item *, comp); 
int addToTree(Tree **, Item *, comp);
int removeFromTree(Tree **, Item *, comp); 
void printTree(Tree *, int); 
Tree *copyToTree(Item *); 
int returnCount(Tree *); 
#endif

Tree.c

/*-------------------------------Tree.c---------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include "Tree.h"
#include <math.h>

Tree *initializeTree(Tree *t){
    if((t = malloc(sizeof(Tree))) == NULL)
            return NULL; 

    t->left = t->right = NULL;
    t->item = NULL;
    t->branches = 0;  
    return t;  
}

int isEmpty(Tree *t){
    return (t->branches == 0) ? 1:0; 
}

int isFull(Tree *root){
    return (root->branches == ((int)pow(2, MAXLEVEL)-1)) ? 1:0;
}

Tree *copyToTree(Item *thing){
    Tree *tmp = initializeTree(tmp); 
    tmp->item = thing; 
    return tmp; 
}

Tree **searchTree(Tree **t, Item *thing, comp f){
    int compare; 

    /*t == NULL || ..*/ 
    if((*t) == NULL || (*t)->item == NULL)
        return NULL; 
    if((compare = f((*t)->item, thing)) == 0)
        return t; 
    else if(compare > 0)
        return searchTree((&((*t)->left)), thing, f);
    else
        return searchTree((&((*t)->right)), thing, f); 
}

int returnCount(Tree *t){
    if(t == NULL)
        return; 
    t->branches = 1 + returnCount(t->left); 
    t->branches += returnCount(t->right);
    return t->branches;  
}

int addToTree(Tree **t, Item *thing, comp f){
    if(*t == NULL || (*t)->item == NULL){
        *t = copyToTree(thing);
        if(*t == NULL)
            return 0;  
        return 1; 
    } 

     if(f((*t)->item, thing) >= 0)
        return addToTree(&((*t)->left), thing, f); 
     else
        return addToTree(&((*t)->right), thing, f); 
}

int removeFromTree(Tree **t, Item *thing, comp f){
    Tree **tmp, *tmp2;
    if((tmp = searchTree(t, thing, f)) == NULL)
        return 0;
    tmp2 = *tmp; 

    if((*tmp)->left == NULL ^ (*tmp)->right == NULL)
        ((*tmp)->right == NULL) ? (*tmp = (*tmp)->left):(*tmp = (*tmp)->right);
    else if((*tmp)->left != NULL && (*tmp)->right != NULL){
        (*tmp) = (*tmp)->left;
        /*tmp3 = *tmp;*/
        while((*tmp)->right != NULL)
            (*tmp) = (*tmp)->right; 
        (*tmp) = tmp2->right; 
    }

    free(tmp2->item);
    free(tmp2);
    return 1;   
}

void printTree(Tree *t, int level){
    if(t == NULL || t->item == NULL)
        return; 

    int spaces = 5*(MAXLEVEL - level); 
    printTree(t->left, level+1);
    while(spaces-- > 0)
        putchar(' '); 
    putchar(level + '0');
    putchar('\n');  
    printTree(t->right, level+1); 
}

Main.c

/*-------------------------------Main.c---------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Tree.h"
#define MAXNAME 20
int itemComp(const Item *, const Item *); 
int promptUser(void); 
Item *createUserItem(); 

int main(){
    Tree *userTree = initializeTree(userTree);  
    Item *userItem; 
    int userInput; 

    do{
        userInput = promptUser(); 

        switch(userInput){
            case 1: 
               if((userItem = createUserItem()) && addToTree(&userTree,userItem,itemComp))
                    puts("Cat successfully added!");
               else
                  puts("Could not add cat!");  
               break;
            case 2:
               if(userItem = createUserItem()){
                  if(removeFromTree(&userTree, userItem, itemComp))
                      puts("Cat successfully removed!"); 
               }
               else
                   puts("Could not remove cat!"); 
               break; 
            case 3: 
               if((userItem =createUserItem()) && searchTree(&userTree,userItem,itemComp))
                   puts("Cat found!");
               else
                   puts("Cat not found!"); 
               break; 
            case 4:
               if(isEmpty(userTree))
                   puts("Tree is empty!");
               else
                   puts("Tree is not empty!"); 
               break; 
            case 5:
               if(isFull(userTree))
                   puts("Tree is full!"); 
               else
                   puts("Tree is not full!"); 
               break; 
            case 6:
               printTree(userTree, 1); 
               break; 
            case 0:
               break;
            default:
               puts("Not an option!"); 
               break;
        }

    }while(userInput);

   return 0;  
}

int promptUser(){
    puts("----------Options Menu-----------");
    puts("1. Add Cat"); 
    puts("2. Remove Cat"); 
    puts("3. Search for cat"); 
    puts("4. Check if Empty"); 
    puts("5. Check if Full"); 
    puts("6. Print Tree"); 
    puts("0. Quit"); 

    int userinput = getchar() - '0'; 
    while(getchar() != '\n')
        ;
    return userinput; 
}

Item *createUserItem(){
    static char nameBuf[MAXNAME];

    puts("Enter cat name: "); 
    if(fgets(nameBuf, MAXNAME, stdin) == NULL)
      return NULL; 

    Item *tmp = malloc(sizeof(Item)); 
    if((tmp->name = malloc(strlen(nameBuf))) == NULL)
      return NULL; 

    strcpy(tmp->name, nameBuf);   

    tmp->age = -1; 
    puts("Enter cat age"); 
    scanf("%d", &tmp->age); 
    while(getchar() != '\n')
        ;

    return tmp;
}

int itemComp(const Item *thing_one, const Item *thing_two){
    int comparison;

    if(comparison = strcmp(thing_one->name, thing_two->name)){
        printf("The comparison is [%d]\n", comparison); 
        return comparison; 
    }

    return thing_one->age - thing_two->age; 
}

The plan was:

If it has no children, just free the memory for the tree;

If the current tree has one child, set the current tree's pointer to that child to be the pointer to the current tree, because the pointer to the current tree is contained within the parent of the current tree. Then free the memory for the current Tree.

If the current tree has two children, set the current tree's pointer to the left child to be the pointer to the current tree (for reasons above), then, traverse the left child's right pointers until there's a vacancy (NULL pointer). Set the current tree's right child to be that vacancy.

Any ideas?

Answer 1

I had to rebuild your remove node function from scratch. Unfortunately I do not think you had the right idea when implementing it yourself. Removing a node from a tree is a hard function to implement, especially when managing memory (to avoid memory leaks).

The idea when removing a node is to replace it with the right-most node in the left subtree of the node that you want to remove. If the left subtree is empty then remove the current node entirely and replace with the right subtree.

It would be something along the lines of this (not tested -- just grasp the general idea of this):

// Purpose: Finds the largest node in the given Tree. Once found, 
//          returns the item and destroys the node.
// PRE: t != NULL, *t != NULL
// POST: - returns a pointer to a Item
//       - Side Effect: Frees the largest node in the Tree. Caller must
//                       free the returned Item.
// TIME: O(n), where n is the height of the Tree.
static Item *largestNode( Tree **t ) {
  assert( t != NULL );
  assert( ( *t ) != NULL );

  if ( ( *t )->right == NULL ) {
    Item *key = ( *t )->item;

    free( *t );

    *t = NULL;

    return key;
  } else {
    return largestNode( &( ( *t )->right ) );
  }
}

Tree *removeFromTree( Tree **t, Item *key, comp f ) {
  // Determines whether we are at an empty node (key is not found).
  if ( ( t == NULL ) || ( ( *t ) == NULL ) )
    return NULL;

  // Defines a temporary Tree pointer, tmp and the result from the 
  // compare function.
  Tree *tmp = *t;
  int const result = f( tmp->item, key );

  // Determines if the result of comparing the current node and the key 
  // is less. If so, recurse on the left subtree. If it is more, recurse 
  // on the right subtree, otherwise we found the node that we want to remove, 
  // remove it.
  if ( result < 0 ) {
    tmp->left = removeFromTree( &( tmp->left ), key, f );
  } else if ( result > 0 ) {
    tmp->right = removeFromTree( &( tmp->right ), key, f );
  } else {
    // Checks if left subtree exists. If not, delete the entire current node 
    // and return the right subtree, otherwise the left subtree exists and we 
    // should find the largest node in the left subtree and replace the current 
    // node item with the item from the largest node in the left subtree then 
    // delete the entirety of the largest node in the right subtree.
    if ( tmp->left == NULL ) {
      Tree *tmp_new = tmp->right;

      free( tmp );
      // @TODO: add free for item.

      return tmp_new;
    } else {
      Item *backup = tmp->item;
      tmp->item = largestNode( &( tmp->left ) );

      // @TODO: add free for backup item.

      return tmp;
    }
  }
}