Thread: Why does my BST program crash when I try to delete a node having grand children?

  1. #1
    Registered User
    Join Date
    May 2018
    Posts
    11

    Why does my BST program crash when I try to delete a node having grand children?

    Code:
    struct node
    {
    int data;
    struct node *left, *right;
    };
    struct node *root=NULL;
    int main()
    {
    root=insert(root,100);
    insert(root,80);
    insert(root,10);
    insert(root,40);
    insert(root,90);
    insert(root,30);
    insert(root,120);
    insert(root,140);
    inorder(root);
    printf("Min: %d Max: %d\n", FindMin(root), FindMax(root)); 
    delete(root,80);
    printf("After deletion:\n");
    inorder(root);
    return 0;
    }
    struct node *insert(struct node *node, int data)
    {
    if(node==NULL)
    {
    return newnode(data);
    }
    else if(data < node->data)
    {
    node->left=insert(node->left, data);
    }
    else if(data > node->data)
    {
    node->right=insert(node->right,data);
    }
    return node;
    }
    struct node *newnode(int data)
    {
    struct node *tmp=(struct node*)malloc(sizeof(struct node));
    tmp->data=data;
    tmp->left=tmp->right=NULL;
    return tmp;
    }
    struct node *inorder(struct node *root)
    {
    if(root!=NULL)
    {
    inorder(root->left);
    printf("%d\n",root->data);
    inorder(root->right); 
    }
    }
    struct node *FindMin(struct node *root)
    {
    if(root==NULL)
    {
    printf("Tree is empty!\n");
    return -1;
    }
    while(root->left!=NULL)
    {
    root=root->left;
    }
    return root->data;
    }
    struct node *FindMax(struct node *root)
    {
    if(root==NULL)
    {
    printf("Tree is empty!\n");
    return -1;
    }
    while(root->right!=NULL)
    {
    root=root->right;
    }
    return root->data;
    }
    struct node *delete(struct node *root, int data)
    {
    if(root==NULL)
    {
    printf("Tree is empty!\n");
    return -1;
    }
    else if(data < root->data)
    {
    root->left=delete(root->left, data);
    }
    else if(data > root->data)
    {
    root->right=delete(root->right, data);
    }
    else
    {
    if(root->left==NULL && root->right==NULL)
    {
    free(root);
    root=NULL;
    }
    else if(root->left==NULL)
    {
    struct node *tmp=root;
    // tmp=root;
    root=root->right;
    free(tmp);
    }
    else if(root->right==NULL)
    {
    struct node *tmp=root;
    // tmp=root;
    root=root->left;
    free(tmp);
    }
    else
    {
    struct node *tmp=FindMin(root->right);
    root->data=tmp->data;
    root->right=delete(root->right,tmp->data);
    }
    }
    return root;
    }
    

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,416
    Try posting a version which isn't filled with font tags from your editor.
    So that the board code tags can present nice looking code.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    May 2018
    Posts
    11
    Well, i found the problem. FindMin and Findmax functions need to return root only. No casting necessary unless you are going to print max and min values.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Quadtree Node -> pointers to the children node
    By yahn in forum C++ Programming
    Replies: 2
    Last Post: 04-13-2009, 06:38 PM
  2. BST - delete node
    By marrk in forum C Programming
    Replies: 5
    Last Post: 12-20-2006, 10:46 AM
  3. delete by copy only for non-children nodes?
    By patricio2626 in forum C++ Programming
    Replies: 17
    Last Post: 11-18-2006, 08:37 AM
  4. Delete node
    By AmazingRando in forum C Programming
    Replies: 1
    Last Post: 09-23-2003, 04:44 PM
  5. Delete node!!!!!
    By khpuce in forum C Programming
    Replies: 3
    Last Post: 05-31-2003, 06:33 AM

Tags for this Thread