How to properly insert/delete in a binary search tree in C?

Question

I kinda have to put my previous C questions on hold cause this one is more important now...

I have already coded the insert and delete functions on my binary search tree but the delete function is incomplete. There's a couple of things I need help in...

1) Is my insert function good or can it be improved somehow?

2) My delete function lacks the deletion of a node with both the left and right childs. I've searched a lot in the past few hours but couldn't find a proper way to do it.

2.a) How should I delete a node with 2 child nodes?

2.b) As in the first question, is the delete function good or can it be improved? This one I know it can because I'm repeating lots of code in those ifs but I don't see how can I improve it, I need help on that too.

typedef struct sClientProfile *ClientProfile;
typedef struct sClientTree *ClientTree;

typedef struct sClientProfile {
    char *clientName;
    int clientAge;
    int clientNIF;
} nClientProfile;

typedef struct sClientTree {
    ClientProfile clientProfile;
    char *clientName;

    ClientTree leftTree;
    ClientTree rightTree;
} nClientTree;

void addClientToTree(ClientTree *cTree, ClientProfile cProfile) {
    if(!*cTree) {
        ClientTree new = (ClientTree)malloc(sizeof(nClientTree));

        if(!new) {
            perror("malloc");
        }

        new->clientName = strdup(cProfile->clientName);
        new->clientProfile = cProfile;

        new->leftTree = NULL;
        new->rightTree = NULL;

        *cTree = new;
    } else {
        if(strcmp((*cTree)->clientName, cProfile->clientName) > 0) {
            addClientToTree(&(*cTree)->leftTree, cProfile);
        } else {
            addClientToTree(&(*cTree)->rightTree, cProfile);
        }
    }
}

void deleteClientFromTree(ClientTree *cTree, char *cName) {
    if(!cTree) return;

    int nCompare = strcmp((*cTree)->clientName, cName);

    if(nCompare > 0) {
        deleteClientFromTree(&(*cTree)->leftTree, cName);
    } else if(nCompare < 0) {
        deleteClientFromTree(&(*cTree)->rightTree, cName);
    } else {
        if(!(*cTree)->leftTree && !(*cTree)->rightTree) {
            ClientTree cliPtr = *cTree;

            free(cliPtr->clientProfile);
            free(cliPtr);

            cliPtr->clientProfile = NULL;
            cliPtr = NULL;

            *cTree = NULL;
        } else if(!(*cTree)->leftTree) {
            ClientTree cliPtr = *cTree;

            free(cliPtr->clientProfile);
            free(cliPtr);

            cliPtr->clientProfile = NULL;

            *cTree = (*cTree)->rightTree;
        } else if(!(*cTree)->rightTree) {
            ClientTree cliPtr = *cTree;

            free(cliPtr->clientProfile);
            free(cliPtr);

            cliPtr->clientProfile = NULL;

            *cTree = (*cTree)->leftTree;
        } else {

            // MISSING DELETE CASE

        }
    }
}

You'll probably notice but let me just make 2 remarks:

• This tree uses strings instead of the normal int representation. That's why I use strcmp() all the way, I think I'm using it right.
• I'm not using recursion, I rather pass the pointer (of a structure pointer in this case) and work with that. It looks more clean somehow and in the future I want to return a success value if a node was deleted.

UPDATE BELOW:
I've already did my iterative version of the delete function but I don't like some things about it, maybe they can be improved (or not) but I can't see how. I've also tried to code the case it was missing, deleting a node with 2 childs, but it's not working as it should...

I've commented the whole code where I think the code can be improved and where's the problem. I've also named those problems as A, B (there's no B anymore), C and D so we can reference to them easily.

bool deleteClientFromTree(ClientTree *cTree, char *cName) {
    if(!cTree) return FALSE;

    ClientTree currPtr = *cTree;
    ClientTree prevPtr = NULL;
    int nCompare;

    while(currPtr) {
        nCompare = strcmp(currPtr->clientName, cName);

        if(nCompare > 0) {
            prevPtr = currPtr;
            currPtr = currPtr->leftTree;
        } else if(nCompare < 0) {
            prevPtr = currPtr;
            currPtr = currPtr->rightTree;
        } else {
            /*
             * A)
             * 
             * The following cases have 3 lines in common, the free()
             * calls and return statement. Is there anyway to improve
             * this code and make it more compact?
             * 
             * Of course, the printf's are to be removed...
             */
            if(!prevPtr && !currPtr->leftTree && !currPtr->rightTree) {
                printf("CASE #1\n");

                *cTree = NULL;

                free(currPtr->clientProfile);
                free(currPtr);

                return TRUE;
            } else if(!currPtr->leftTree || !currPtr->rightTree) {
                printf("CASE #2\n");

                if(prevPtr->leftTree == currPtr) {
                    prevPtr->leftTree = currPtr->rightTree;
                } else {
                    prevPtr->rightTree = currPtr->leftTree;
                }

                free(currPtr->clientProfile);
                free(currPtr);

                return TRUE;
            } else {
                printf("CASE #3\n");

                ClientTree tempPtr = currPtr->rightTree;

                while(tempPtr->leftTree) {
                    tempPtr = tempPtr->leftTree;
                }

                /*
                 * C)
                 * 
                 * This has a big problem...
                 * 
                 * If you take a look at the ClientProfile structure,
                 * in the first post, you'll see two ints
                 * (clientNIF/clientAge) and one char* (clientName).
                 * 
                 * The problem is that the following code line is only
                 * copying the integer data, not the string. For some
                 * reason, the string remains the old one.
                 * 
                 * I tried to use strdup() directly on clientName like:
                 * currPtr->clientProfile->clientName = strdup(tempPtr->clientProfile->clientName);
                 * but it still doesn't work.
                 * 
                 * Why everything is being copied but the strings?
                 */
                currPtr->clientProfile = tempPtr->clientProfile;

                /*
                 * D)
                 * 
                 * Is there anyway to not call the function itself
                 * and make the while loop once again and delete the
                 * corresponding leaf?
                 */
                return deleteClientFromTree(&currPtr->rightTree, tempPtr->clientProfile->clientName);
            }
        }
    }

    return FALSE;
}

Solution 1

First off, you mentioned you aren't using recursion but each function has a logical path that calls itself.

On to the questions:

1) Remove the recursion. This can get you in a lot of trouble if your tree is large enough to blow your stack. Gcc has limited support for tail recursion, but I wouldn't count on it.

2) Typically, when you delete a child with two nodes, you promote the left or right node to the position the deleted node was in. (This is a highly simplistic case, I'm assuming your tree isn't balanced)

2.b) Your delete code has some problems. I'd recommend walking through it with a few hypothetical situations. Immediately obvious to me was free'ing a pointer and then deferencing it:

free(cliPtr);

cliPtr->clientProfile = NULL;

Of course, you can always worry about style once you get the correctness thing squared away.

Solution 2

Ideally there are three cases for deletion of a node in BST:

Case 1:

X has no children: remove X

Case 2:

X has one children : Splice out X

Case 3:

X has two children : swap X with its successor and follow case #1 or #2

So for the missing delete case:

When X (node to delete) has two children, replace X with the successor of X and follow case #1 or case #2. You can also replace with its predecessor, might be a good alternative.

if ( X->left && X->right) {

NODE *Successor = FindSuccessor(X);
X->data = Successor->data;
free(Successor);

}

Solution 3

this binary codes are insert, delete,search, and quit. Examples:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Binary Tree {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        LinkedList ll = new LinkedList();

        ll.add("\n"+"mai    0020");
        ll.add("\n"+"king   0019");
        ll.add("\n"+"maan   0002");
        ll.add("\n"+"dimple 0024");
        ll.add("\n"+"eman   0004");
        ll.add("\n"+"lara   0005");
        ll.add("\n"+"cute   0008");
        ll.add("\n"+"irene  0011");
        ll.add("\n"+"sheena 0030");
        ll.add("\n"+"aisy   0003");

        System.out.println("display: " + ll);
        System.out.println("\n\n");

        for(int c=0; c<=10; c++) {
            System.out.println("select from: 1-insert, 2-delete," + 
                               " 3-display, 4-search, 5-quit");

            String x = br.readLine();
            int y = Integer.parseInt(x);
            switch (y) {
                case 1: //inserting
                    System.out.println("input name");
                    String n= br.readLine();
                    System.out.println("input a list number");
                    String o = br.readLine();
                    int z = Integer.parseInt(o);
                    ll.add("\n"+n+" "+z);
                    break;
                case 2: // delete   
                    ll.removeFirst();
                    break;
                case 3: //Display
                    System.out.println("\n\n"+"List of employee: " + ll);       
                    System.out.println("\n\n");
                    break;
                case 4: //search
                    System.out.println("\n");
                    System.out.println("Search");

                    System.out.println("first element of the Linkedlist is: "
                                       + ll.getFirst());
                    System.out.println("\n\n");
                    System.out.println("last element of linkedlist:"
                                       + ll.getLast());     
                    break;
                case 5: //quit
                    System.out.println("\n\n\n\n\n" 
                                       + " Thank You Very Much!!!!!!!\n\n\n");
                    System.exit(0);
                    break;
            }
        }
    }
}