Thread: Segmentation fault when deleting node from BST, using double pointers

  1. #1
    Registered User
    Join Date
    Apr 2008
    Posts
    7

    Segmentation fault when deleting node from BST, using double pointers

    Hi Guys, can you please point out what could be the issue with code below. I guess I m doing something wrong with pointers maintenance however from my perspective this code should be ok.

    What I am doing is:
    1. Create tree and populate it with nodes. -- OK
    2. Print tree. --- OK
    3. Locate node to be removed. -- OK
    3. Delete particular node (logic seems to be OK) however I get segmentation fault all the time once I am trying to free() node that has to be removed.

    Please help.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node *tree;
    
    struct node {
        int key;
        tree left;
        tree right;
    };
    
    void InsertKey(tree *tr, int key) {
        if (*tr == NULL) {
            if ( (*tr=(tree)malloc(sizeof(tree))) == NULL) {
                printf("Can not allocate root\n");
                exit(1);
            }
            (*tr)->key=key;
            (*tr)->left=NULL;
            (*tr)->right=NULL;    
        }
        else {
            if (key<(*tr)->key)
                InsertKey(&(*tr)->left, key);
            else
                InsertKey(&(*tr)->right, key); 
        }
    }
    
    void PrintKey(tree *tr) {
        if (*tr == NULL)
            return;
        else {
        printf("Value of item is %d\n", (*tr)->key);
        PrintKey(&(*tr)->left);
        /*printf("Value of item is %d\n", (*tr)->key);*/
        PrintKey(&(*tr)->right);
        }
    }
    
    tree SearchTree(tree tr, int key) {
    	if (tr==NULL) /* tree is empty*/
    		return NULL;
    	else if (tr->key>key) /* search left subtree*/
    		return SearchTree(tr->left, key);
    	else if (tr->key<key) /* search right subtree*/
    		return SearchTree(tr->right, key);
    	else
    		return tr;
    }
    
    void DeleteNodeR(tree *tr) {
    	if ((*tr)->left==NULL && (*tr)->right==NULL) {
    		tree tmp=*tr;
    		*tr=NULL;
    		free(tmp);
    		tmp=NULL;
    	}
    	else if ((*tr)->left==NULL) {
    		tree root=*tr;
    		*tr=(*tr)->right;
    		free(root);
    		
    	}
    	else if ((*tr)->right==NULL) {
    		tree root=*tr;
    		*tr=(*tr)->left;
    		free(root);
    		
    	}
    	else { /* node has both children, get right most node from left subtree */
    		tree iterateLeftTree=(*tr)->left;
    		while (iterateLeftTree->right!=NULL)
    			iterateLeftTree=iterateLeftTree->right;
    		(*tr)->key=iterateLeftTree->key;
    		free(iterateLeftTree);
    		iterateLeftTree=NULL;
    	}
    }
    
    int main(void) {
        tree tr=NULL;
        tree locatedNode=NULL;
    
        InsertKey(&tr, 15);
        InsertKey(&tr, 20);
        InsertKey(&tr, 10);
    
        PrintKey(&tr);
        locatedNode=SearchTree(tr,10);
        printf("Remove node %d\nTree after removal\n", locatedNode->key);
        DeleteNodeR(&locatedNode);
        PrintKey(&tr);
        return 0;
    }
    Thank you.

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Code:
    typedef struct node *tree;
    Please don't do that. That is the worst possible way to abuse a pointer typedef.
    It's better to remove it completely and use node** instead. No confusion there.
    Consider it a suggestion.
    Last edited by Elysia; 04-28-2008 at 02:28 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Feel free to ignore what Elysia just wrote. You're not doing anything wrong. That one poster just happens to dislike that style.
    I shudder to think what Elysia thinks of the Windows API that is full of pointer typedefs like LPCSTR.

    I'm not seeing any obvious problem, but I haven't run your program yet.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Feel free to ignore iMalc.
    Pointer typedefs complicate the program and makes it prone to errors. Plus it's MORE to type than NOT using them (usually).
    Using pointer typedefs will bite you later. ESPECIALLY a pointer typedef that is inapproperitly named (as yours is).
    A tree is not a pointer; it's an object.

    So let me ask another question instead. Why is it so hard to do
    typedef struct node node;
    And do
    node**
    instead?

    Typedefs are good at hiding complex syntax into something more readable, but this obfuscates the reading by hiding the fact that it's a pointer, so it makes it harder to read.
    Last edited by Elysia; 04-28-2008 at 02:24 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    In this case the bug is actually caused by this line:
    Code:
            if ( (*tr=(tree)malloc(sizeof(tree))) == NULL) {
    sizeof(tree) is the size of a pointer. You want sizeof(*tree) or sizeof(struct node).

    Regardless of the fact that it possibly did hide the error in this case, it's up to you whether you remove the typedef or not. I can certainly agree that it wasn't named in the best manner, but that isn't grounds for getting rid of it, more for giving it a better name.
    Last edited by iMalc; 04-28-2008 at 02:50 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Note that I'm not demanding that you should get rid of it. It's a suggestion. Your typedef hid a little problem right there because it was inappropriately named.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    The OP probably could easily have made more errors (but for different reasons) if he had to deal with ** all over the place.
    Last edited by iMalc; 04-28-2008 at 02:51 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    It was badly written. Since you "reacted" I edited it to outline it in a nicer way, to add that it was a suggestion. The way it should be.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Alright, I'll concede to that.
    I guess I started with an opening that got your back up, and it went downhill from there.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By brb9412 in forum C Programming
    Replies: 16
    Last Post: 01-04-2009, 04:05 PM
  2. Conversion From C++ To C
    By dicon in forum C++ Programming
    Replies: 2
    Last Post: 06-10-2007, 02:54 PM
  3. need some help with last part of arrays
    By Lince in forum C Programming
    Replies: 3
    Last Post: 11-18-2006, 09:13 AM
  4. question about a working linked list
    By cold_dog in forum C++ Programming
    Replies: 23
    Last Post: 09-13-2006, 01:00 AM
  5. Replies: 2
    Last Post: 11-28-2003, 11:50 AM