CODEWITHSUNDEEP
cbinary-search-treenodes
skornos
skornos

Reputation: 3301

Binary search tree node deletion

I am implementing a function for the node removal from the binary search tree. The prototype of the function is set and I can't change it, it is a school assignment. My code:

typedef struct tBSTNode {
    char Key;                                                                 
    struct tBSTNode * LPtr;                                
    struct tBSTNode * RPtr;  
} *tBSTNodePtr; 

void BSTDelete (tBSTNodePtr *RootPtr, char K) {
  tBSTNodePtr *tmp;

  if (*RootPtr != NULL) {
    if (K < (*RootPtr)->Key)
        BSTDelete(&(* RootPtr)->LPtr, K);
    else if (K > (*RootPtr)->Key)
        BSTDelete(&(* RootPtr)->RPtr, K);
    else {
            if ((* RootPtr)->LPtr == NULL) {
                /* there is only right branch or none*/
                tmp = RootPtr;
                *RootPtr = (* RootPtr)->RPtr;
                free(*tmp);
                *tmp = NULL;
            }
            else if ((* RootPtr)->RPtr == NULL) {
                /* there is only left branch or none*/
                tmp = RootPtr;
                *RootPtr = (* RootPtr)->LPtr;
                free(*tmp);
                *tmp = NULL;
            }
            else
                /* there are both branches, but that is for another topic*/
        }
    }
}

This code works correctly just in case when there are no branches connected to the node I am deleting. I expect that there is a problem with *tmp = NULL; line and I am losing my address to the rest of the branch but on the other hand if this line isn't included I am getting a SEGFAULT and I am trying to figure out why.

EDIT:

ok, now I know where the mistake was. It is stupid mistake, I should have used tBSTNodePtr tmp; instead of tBSTNodePtr *tmp;

Upvotes: 0

Views: 351

Answers (2)

Pheu Verg
Pheu Verg

Reputation: 230

you have problems with using pointers. If we have sometype *ptr and we check if this ptr adresses some space we write (ptr!=NULL). *ptr is refering to the value itself, for example to your structre. Read more about pointer types in C.

Upvotes: 1

Bhavik Shah
Bhavik Shah

Reputation: 5183

your logic for deleting is wrong

 if ((* RootPtr)->LPtr == NULL) {
                /* there is only right branch or none*/
                tmp = RootPtr;
                *RootPtr = (* RootPtr)->RPtr;
                free(*tmp);
                *tmp = NULL;
            }

in this code you are deleting the required node but not adding the child root of that node

 if ((* RootPtr)->LPtr == NULL) {
                /* there is only right branch or none*/
                tmp = RootPtr;
                *RootPtr = (* RootPtr)->RPtr;
                free(*tmp);
                *tmp = NULL;
                insert(RootPtr);  //insert the child node again in the tree
            }

Upvotes: 0

Related Questions