Help with insert/delete binary search tree

I kinda needed to have this finish by now (first phase of a school project) but I wasn't able to finish it within the deadline... But I still have to do it so I can advanced to other things for the second phase and I need help with this binary search tree.

I have already coded the insert and delete functions 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.

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.

Now, my code:

Code:

---

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
                       
                }
        }
}

---

Little bump... :(

Quote:

---

Originally Posted by Nazgulled

I'm not using recursion

---

Actually you are using recursion. In fact you are exclusively using recursion and never using iteration - there are no loops at all in the posted code.
Perhaps you meant to say that you are not using iteration?

Deletion of a node with two children is done by finding the maximum node of the left-subtree, removing that form the tree, and re-inserting it in place of the node you wish to delete.
(Or the minimum node of the right subtree)

You're right... Actually, what I mean was that I wasn't using recursion in the sense of returning a value, instead, I pass the address of structure as an argument. I misunderstood what I wanted to say...

Someone else suggested me to use iteration over recursion because of possible stack problems. But I have no clue on how could I do a delete function of a binary search tree, or even just a "print-all-nodes-and-childs" functions without using recursion. I can do that with a linked-list, I just need to use "while" one time, but for a binary search tree with 2 childs? How do I do that? Also, the same person said something about freeing a pointer and then deferencing it:

Code:

---

free(cliPtr);

cliPtr->clientProfile = NULL;

---

Is there anything wrong with this?

Quote:

---

Originally Posted by Nazgulled

Someone else suggested me to use iteration over recursion because of possible stack problems. But I have no clue on how could I do a delete function of a binary search tree, or even just a "print-all-nodes-and-childs" functions without using recursion. I can do that with a linked-list, I just need to use "while" one time, but for a binary search tree with 2 childs? How do I do that? Also, the same person said something about freeing a pointer and then deferencing it:

Code:

---

free(cliPtr);

cliPtr->clientProfile = NULL;

---

Is there anything wrong with this?

---

Hadn't looked close enough to notice that. Yeah that's a bad thing to do. If you're lucky it might work a few times, but then it'll go boom sooner or later. You must not access or write to a structure after it has been freed.
In this case you can just delete this line:

Code:

---

cliPtr->clientProfile = NULL;

---

There's no point setting something to NULL when it's going out of existence.

Converting tail-recursion into iteration is not particularly hard. However if the function makes two recursive calls then only one of them can be turned into iteration.

I'll illustrate how one can make a tree node counting function semi-iterative.
Double Recursion:

Code:

---

// Returns the number of items in the tree
int TreeCount(const TItem *head) {
        int count = 0;
        if (head != NULL) {
                //recursively count left nodes (add one for this node)
                count += TreeCount(head->left) + 1;
                //recursively count right nodes
                count += TreeCount(head->right);
        }
        return count;
}

---

Semi Iterative / Semi Recursive:

Code:

---

// Returns the number of items in the tree
int TreeCount(const TItem *head) {
        int count = 0;
        while (head != NULL) {
                //recursively count left nodes (add one for this node)
                count += TreeCount(head->left) + 1;
                //iteratively count right nodes
                head = head->right;
        }
        return count;
}

---

Quote:

---

Originally Posted by iMalc

Hadn't looked close enough to notice that. Yeah that's a bad thing to do. If you're lucky it might work a few times, but then it'll go boom sooner or later. You must not access or write to a structure after it has been freed.
In this case you can just delete this line:

Code:

---

cliPtr->clientProfile = NULL;

---

There's no point setting something to NULL when it's going out of existence.

---

Hum... When I use free on something and if in the next line I try to print it's value anyways, the value will still be there, that's why I set the variable to NULL. To make sure it's cleaned.

I guess free cleans that memory block and the data will still be there until something else overwrites it and it's the day it's supposed to work, right?

Hum... After searching a bit for iteration on binary trees I found an algorithm for iterative insert, here's what I did:

Code:

---

void addClientToTree(ClientTree *cTree, ClientProfile cProfile) {
        if(!*cTree) {               
                *cTree = newClientTreeNode(cProfile);
                return;
        }
       
        ClientTree currPtr = *cTree;
        int nCompare;
       
        do {
                nCompare = strcmp(currPtr->clientName, cProfile->clientName);
                       
                if(nCompare > 0) {
                        if(!currPtr->leftTree) {
                                currPtr->leftTree = newClientTreeNode(cProfile);
                                return;
                        } else {
                                currPtr = currPtr->leftTree;
                        }
                } else if(nCompare < 0) {
                        if(!currPtr->rightTree) {
                                currPtr->rightTree = newClientTreeNode(cProfile);
                                return;
                        } else {
                                currPtr = currPtr->rightTree;
                        }
                }
        } while(currPtr && nCompare != 0);
       
        return;
}

---

Code:

---

ClientTree newClientTreeNode(ClientProfile cProfile) {
        ClientTree newClient = malloc(sizeof(nClientTree));
       
        if(!newClient) perror("malloc");
               
        newClient->clientName = strdup(cProfile->clientName);
       
        if(!newClient->clientName) perror("strdup");
       
        newClient->clientProfile = cProfile;
       
        newClient->leftTree = NULL;
        newClient->rightTree = NULL;
       
        return newClient;
}

---

I guess it's ok now?

I'll try to convert my delete function into iteration and see if I can also delete a nod with 2 child's...

Quote:

---

Originally Posted by Nazgulled

Hum... When I use free on something and if in the next line I try to print it's value anyways, the value will still be there,

---

How do you know it?
memory does not belongs to your program - it is returned to the memory pool...

if this free just returned the last chunk of the memory in some page - the whole page could be already returned to the OS making any address inside this page not available to the program at all.

So even read operation from this address could cause a GPF

I don't, what I was trying to say is that if I use printf() right after free(), normally, I still see the stuff I freed...

Quote:

---

Originally Posted by Nazgulled

I don't, what I was trying to say is that if I use printf() right after free(), normally, I still see the stuff I freed...

---

pure luck

Quote:

---

Originally Posted by Nazgulled

I don't, what I was trying to say is that if I use printf() right after free(), normally, I still see the stuff I freed...

---

Well, then yes, it would be a good idea to set the pointer to be a null pointer if you have code that follows that will not immediately reuse the pointer. It is better to have a null pointer than a dangling pointer since you can check for a null pointer, but you cannot check for a dangling pointer.

Quote:

---

Originally Posted by laserlight

Well, then yes, it would be a good idea to set the pointer to be a null pointer if you have code that follows that will not immediately reuse the pointer. It is better to have a null pointer than a dangling pointer since you can check for a null pointer, but you cannot check for a dangling pointer.

---

That's the word lol... I've read a document before on "dangling pointer" and it was somewhat bad and to set it as NULL to solve it. That's why I'm setting every pointer I free to NULL.

Normally, no, the code that follows the free() is not going to reuse that pointer because when I free() something, it's normally in linked lists or binary trees delete functions (like in the delete function in my first post).

So, should or should I not set the pointers to NULL?

Quote:

---

Originally Posted by laserlight

Well, then yes, it would be a good idea to set the pointer to be a null pointer if you have code that follows that will not immediately reuse the pointer. It is better to have a null pointer than a dangling pointer since you can check for a null pointer, but you cannot check for a dangling pointer.

---

Besides attempts to access NULL pointer usually provide far clearer trace than access for invalid, non NULL pointer...

Quote:

---

Originally Posted by Nazgulled

Normally, no, the code that follows the free() is not going to reuse that pointer because when I free() something, it's normally in linked lists or binary trees delete functions (like in the delete function in my first post).

So, should or should I not set the pointers to NULL?

---

As iMalc noted, if the pointer is going to go out of scope immediately thereafter, there is no point, other than as a form of paranoid defensive programming to pre-empt modification of the code.

It is indeed fine to set a pointer to NULL immediately after it was freed. However, if you do this:

Code:

---

                        cliPtr->clientProfile = NULL;
                        cliPtr = NULL;

---

then you can remove the first line, since cliPtr is NULL, and there is no way to get to clientProfile by way of that pointer. [Assuming of course there are no other pointers pointing to the memory held in cliPtr - we hope so in this case, as you've just freed the memory, and using pointers after free, even to just set the pointer inside it to NULL, is a bad idea].

--
Mats

I think I get the picture now, thank you...

Still, nobody commented on my attempt to do the insert function as iterative instead of recursive, I suppose there's nothing really wrong about it?

It looks about right (without actually testing it, it's hard to tell). I have some concerns:
Is there any chance you end the loop because currptr == NULL? If so, you end the loop without inserting, which is probably not what you wanted. If there isn't any such chance, then perhaps you should remove the condition, and instead add it as an assert within the loop itself.

If you do that, then you can probably make it an infinite while/for loop and put a "if (cCompare == 0) return;" just after the strcmp - since that makes it much clearer what you actually do.

--
Mats

You are right, supposing my code is working as it should and malloc/strdup do not fail, that condition will never be met because an element will always be inserted into the tree.

Quote:

---

(...)then perhaps you should remove the condition, and instead add it as an assert within the loop itself.

---

I didn't understood this though...

Lets just say that NULLing a pointer that is part of a struct that is being freed is like opening up a text document, typing X's over the whole thing, saving the file, putting it in the recycle bin and then emptying the bin.
You do it only if you're really paranoid.

But if I don't NULL the pointers, won't the OS or any other application be able to access the data on that memory block? It's not important for the application I'm going, but isn't that like a security risk or something?

Quote:

---

Originally Posted by Nazgulled

But if I don't NULL the pointers, won't the OS or any other application be able to access the data on that memory block? It's not important for the application I'm going, but isn't that like a security risk or something?

---

The only risk with a pointer that is not set to NULL is that some part of your application tries to use it, and it's been assigned for some other purpose, e.g.:

Code:

---

#include <stdio.h>
#include <stdlib.h>

int main()
{
  char *q;
  char *p = malloc(15);
  strcpy(p, "Hello, World");
  free(p);
  q = malloc(15);
  strcpy(q, "World, Hello");
  printf("%s\n", p);
  return 0;
}

---

Whilst it's not guaranteed, this most likely will print "World, Hello" - it may print "Hello, World" or some completely different thing.

If the memory is freed, and there is no variable holding a pointer to the memory, it is not available to use [without serious tricking about - and even then, it's pretty pointless, because there is no benefit from being able to access unused memory in the current process, it will for example not allow anyone access other processes memory or gain privileges, and even if that was the case, setting the pointer itself to NULL will not help].

--
Mats

So, you're saying that even setting the pointer to NULL does not prevent some smart guy to read the data that I freed (supposing it wasn't overwritten yet) if he really wanted to?

If that's the case, I think I see the whole picture now...

Quote:

---

Originally Posted by Nazgulled

So, you're saying that even setting the pointer to NULL does not prevent some smart guy to read the data that I freed (supposing it wasn't overwritten yet) if he really wanted to?

If that's the case, I think I see the whole picture now...

---

Correct.

However, that only applies within the current process - other processes (unless they have debug privileges, e.g. Admin rights or possibly running as the same user) are not able to see what's inside your process in any way.

Setting the pointer to NULL only makes it harder to figure out where the memory was, but it doesn't make the memory itself change in any way - if you are really paranoid, clear the contents after use [but what's to stop someone with skills to access it before it's been freed?]

--
Mats

Quote:

---

Originally Posted by matsp

(...)are not able to see what's inside your process in any way.

---

This is the only thing I still don't get. If I freed the memory block some pointer was pointing at, that memory block does not belong to my program/process anymore. And thus, other processes can access that memory block if they knew the memory address... Is this incorrect somehow?

Quote:

---

Originally Posted by Nazgulled

This is the only thing I still don't get. If I freed the memory block some pointer was pointing at, that memory block does not belong to my program/process anymore. And thus, other processes can access that memory block if they knew the memory address... Is this incorrect somehow?

---

no, adresses are per process

Quote:

---

Originally Posted by Nazgulled

But if I don't NULL the pointers, won't the OS or any other application be able to access the data on that memory block? It's not important for the application I'm going, but isn't that like a security risk or something?

---

A pointer is essentially just a number, an address. Setting it to NULL is like scribbling over the address before shredding the piece of paper it is on (And you were going to shred it regardless).

Even if something looked at a block of freed memory it would have little idea which parts of it were pointers and which parts weren't. It's all just random bytes as far as anything else is concerned.

Ok then, thanks for all that insight on pointers.

Now I'm having problems with the real issue on this topic... 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, C and D so we can reference to them easily.

Code:

---

bool deleteClientFromTree(ClientTree *cTree, char *cName) {
        if(!cTree) {
                return FALSE;
        }
       
        ClientTree currPtr = *cTree;
        ClientTree prevPtr = NULL;
        int nCompare;
       
        while(1) {
                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 5 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) {
                                printf("CASE #1: DELETE ROOT NODE\n");
                               
                                *cTree = NULL;

                                free(currPtr->clientProfile);
                                free(currPtr);
                               
                                return TRUE;
                        } else if(!currPtr->leftTree && !currPtr->rightTree) {
                                printf("CASE #2: DELETE LEAF (NO CHILDREN)\n");
                               
                                /*
                                * B)
                                *
                                * Any better way to merge this 2 statements into one?
                                *
                                * I only need to set one of them as null depending
                                * on which node I'm deleting, I could place an if
                                * to check which one, but it would be almost the same
                                * as what I'm doing now.
                                *
                                * Maybe is there a better way to do this?
                                */
                                prevPtr->leftTree = NULL;
                                prevPtr->rightTree = NULL;
                               
                                free(currPtr->clientProfile);
                                free(currPtr);
                               
                                return TRUE;
                        } else if(!currPtr->leftTree) {
                                printf("CASE #3: DELETE NODE WITH RIGHT CHILD\n");
                               
                                prevPtr->leftTree = currPtr->rightTree;
                               
                                free(currPtr->clientProfile);
                                free(currPtr);

                                return TRUE;
                        } else if(!currPtr->rightTree) {
                                printf("CASE #4: DELETE NODE WITH LEFT CHILD\n");
                               
                                prevPtr->rightTree = currPtr->leftTree;
                               
                                free(currPtr->clientProfile);
                                free(currPtr);
                               
                                return TRUE;
                        } else {
                                printf("CASE #5: DELETE NODE WITH 2 CHILDS\n");
                               
                                // Finds the logical successor and places it into: tempPtr
                                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);
                        }
                }
        }
}

---

if your node is not present in the tree - your function will crash

when you deleting leaf - why do you set to NULL both pointers of the father? you delete only one child - second is leaked

also - how you choose what leg of the father to replace has no logic in it

Quote:

---

Originally Posted by vart

if your node is not present in the tree - your function will crash

---

You're right, I forgot about that. I replaced while(1) by while(currPtr) that should take of the problem.

Quote:

---

Originally Posted by vart

when you deleting leaf - why do you set to NULL both pointers of the father? you delete only one child - second is leaked

---

As I explained in the code, the parent will have only one child and I need to set the pointer to that child as NULL. But I don't see how can I find which node pointer (left or right) should I set as NULL and so, I set both. It will work anyway cause one of them is already NULL, the other isn't.

Like I said, I wanted to make that in one line, better, in one statement, but I can't see how can I do it...

Quote:

---

Originally Posted by vart

also - how you choose what leg of the father to replace has no logic in it

---

This one I don't understand...

And just so no one concentrates only in the issues pointed by vart, please note that the code blocks I commented :)

why do you think parent will have 1 child?

Code:

---

A
/ \
B C
 /  \
D  E

---

if I want to delete B - parent has 2 childs, settign both pointers to NULL will leak CDE

I see the problem now, but I don't know how to fix it :/

what will be the value of A->leftTree pointer?

a->leftTree = prevPtr->leftTree = currPtr

these are all equal...

Quote:

---

Originally Posted by Nazgulled

a->leftTree = prevPtr->leftTree = currPtr

these are all equal...

---

so? it means...

I don't know...

Please, can't you just help me? I've been around this function for the past 4 hours, my brain is about to explode, I just can't find my way around to fix it...

if prevPtr->leftTree == currPtr

it means you are on the LEFT side of the parent

if prevPtr->rightTree == currPtr

it means you are on the RIGHT side of the parent

About the reading memory after freeing it etc. I'll try to shed some light on this topic, and I hope if the more experienced guys spot a problem in my explanation, they will further teach both me and you :)

I will be talking in linux point of view, but I assume that most modern systems do it in somewhat similar manner. Of course there's some realtime systems (like OSE), in which all memory is available to all brogram blocks (Eg. processes), but I assume you're talking about some desktop system.

So when we simplify enough we can say following. . Most modern OSes do map the real physical memory into virtual memory addresses, and give to each process their own virtual address space. Actually, in most modern computer systems, we have a hardware memory management unit which handles conversions from virtual addresses to physical memory and vice versa. So basically, at user space (which is basically all applications that aren't either part of the kernel, or a kernel module) it is not possible to access straight to hardware (memory or other hardware). Hardware is invisible for userspace processes, it can only be accessed via drivers written in kernel space. (drivers offer interface for user space applications). [[There is a workaround, but let's not mess with it now]].

So process cannot directly access to RAM.

When we launch a process, certain virtual address space is given to it (and certain physical ran corresponding to it, but the process has no means to get direct HW addresses). The process has no access outside of this sandbox. When we launch another process, it will have it's own virtual address space, and it's own corresponding physical ram. If process is running out of ram, kernel has means to increase it.

If another process tries to access outside of it's sandbox, Eg. requests reading from / writing to location which is not in it's address space, MMU will wake up the kernel, which will check out what is happening. If request was illegal, kernel will generate signal SIGSEGV, and send it to your program. => segmentation fault.

However physical ram is not cleaned, and the amount assigned to each process may change. There's also possibility of swapping, where some memory pages are written temporarily to hard disk, to free up some ram for other purposes.

So basically, it indeed is possible that there is leftowers of data written by your program in the memory. But there should be no traces where in the physical ram your data was, so knowing which bytes belonged to what program - not to mention what were these bytes used for - is quite close to impossible. I say quite close because I've never considered that, and I do not have any accurate information how possible it could be.

If I go a little further off topic to see if I have understood it correctly (I believe there is far more experienced fellows amongst us - who will correct me if I go wrong), there is at least following benefits of having physical addresses hidden:

1. Security. No user space process has access to go and mess the HW as they want - they need to use drivers, which should be written in such a manner that hugest hazards are not possible...

2. Per process memory mapping. If memory would be accessible between processes... Oh joy. If you have ever attempted to build huge and complicated multithreaded software you know what I mean. It really is a mess. Use of one uninitialized pointer may crash anything anywhere, or just make generally bizarre things to happen.

I guess steps 1 and 2 could be implemented even if the applications could access ram directly - but I am not sure how easy / difficult it would be.

3. Shared libraries. Shared libraries are loaded to memory during runtime. When each process has their own virtual address space, shared libraries can be downloaded to physical memory only once. The same physical memory block containing the library can then be mapped for each process' address space.

Finally, the inter process communication often uses "creature" called shared memory. processes can request a shared memory block from kernel, which will then map some physical memory chunk to more than one process' virtual address space. Note however that virtual addresses in different processes need not to be the same, even though they point at same physical ram. Hence shared memory is usually accessed according to the offsets from the start of the memory pool.

However, note that when you quit your program, the shared memory is not automatically freed. (thanks to brewbuck for confirmation ;) ). It will stay accessible (if it was created to be accessible).

And finally the [[]] which I wrote at the beginning. It is possible to write a driver, which can map some real hardware addresses to shared memory, which can then furthermore be mapped by a user space process. That way the HW can be accessed directly by a user space application.


And now that I read this, I am just thinking if I should press the submitt or delete - I am unsure whether this really clarifies anything :D


EDIT: It seems like someone had time to actually give adviece on topic, meanwhile I was babbling :/

Quote:

---

Originally Posted by vart

if prevPtr->leftTree == currPtr

it means you are on the LEFT side of the parent

if prevPtr->rightTree == currPtr

it means you are on the RIGHT side of the parent

---

I see what you mean now... I'm sorry but I'm waaaaaay behind schedule for this and when things like this take more time than it should and I can't figure it out after countless hours debugging, I begin to loose it...

That made see I could improve my function a little bit as per point A) but I wouldn't mind to improve it even further, anyway, here's the updated version, which I suppose has all those problems fixed:

Code:

---

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

---

The most important problem is C) of course, I need that fixed so the function fully works, at least... I can't understand why the string is not being copied...

Your case #1 and #3- D case has problems

Code:

---

A
 / \
B C
    \
    D

---

try to delete A and see what will happen?

Replacing:

Code:

---

if(!prevPtr)

---

By:

Code:

---

if(!prevPtr && !currPtr->leftTree && !currPtr->rightTree)

---

Fixes it right?

My test tree is inserted in this order: H, F, P, G, L, Z and the output you see is in-order. In the following output I'm trying to remove "H", which is the root node... As you can see, first is called case #3 because there are 2 child nodes and then case #2.

As far as I can see, everything is working, apart from the string that is not copied... Element "L" (in-order successor) values (50 and 5000000) were copied to the "H" element, but no the string "L", I honestly can't understand why this isn't being copied...

Code:

---

nazgulled ~/LI3 $ make && ./atulco
gcc -O2 -Wall -g -c atulco.c
gcc -O2 -Wall -g -o atulco atulco.o cities.o clients.o debug.o

F (20, 2000000)
G (40, 4000000)
H (10, 1000000)
L (50, 5000000)
P (30, 3000000)
Z (60, 6000000)

CASE #3
CASE #2
F (20, 2000000)
G (40, 4000000)
H (50, 5000000)
P (30, 3000000)
Z (60, 6000000)

---

I think I fixed all my problems, let's hope so...

Here's my (supposed) final code:

Code:

---

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 {
                       
                        if(currPtr->leftTree && currPtr->rightTree) {
                                printf("CASE #3: NODE WITH 2 CHILDS\n");
                               
                                ClientTree tempPtr = currPtr->rightTree;
                               
                                while(tempPtr->leftTree) {
                                        tempPtr = tempPtr->leftTree;
                                }
                               
                                currPtr->clientName = tempPtr->clientProfile->clientName;
                               
                                currPtr->clientProfile = newClientProfile(
                                        tempPtr->clientProfile->clientName,
                                        tempPtr->clientProfile->clientAge,
                                        tempPtr->clientProfile->clientNIF
                                );

                                cName = tempPtr->clientProfile->clientName;
                               
                                prevPtr = currPtr;
                                currPtr = currPtr->rightTree;
                        } else {
                                if(!prevPtr && !currPtr->leftTree && !currPtr->rightTree) {
                                        printf("CASE #1: ROOT NODE\n");
                                       
                                        *cTree = NULL;
                                } else {
                                        printf("CASE #2: LEAF OR SINGLE CHILD\n");
                                       
                                        if(prevPtr->leftTree == currPtr) {
                                                prevPtr->leftTree = currPtr->rightTree;
                                        } else {
                                                prevPtr->rightTree = currPtr->leftTree;
                                        }
                                }
                               
                                free(currPtr->clientProfile);
                                free(currPtr);
                               
                                return TRUE;
                        }
                }
        }
       
        return FALSE;
}

ClientProfile newClientProfile(char *cName, int cAge, int cNIF) {
        ClientProfile cProfile = malloc(sizeof(nClientProfile));
       
        if(!cProfile) perror("malloc");
       
        cProfile->clientName = strdup(cName);
       
        if(!cProfile->clientName) perror("strdup");
       
        cProfile->clientAge = cAge;
        cProfile->clientNIF = cNIF;
       
        return cProfile;
}

---

Is it ok now?

/me crosses fingers!