Thread: delete minimum in BST problem

Code:

struct node
{ int data;
   struct node* left;
   struct node* right;
};

in main i create struct node* root, and insert other nodes, after this I apply this function to root:

Code:

void deleteMin(struct node* t){
      struct node* temp;
      if(t!=NULL){
         if(t->left!=NULL) 
            deleteMin(t->left);
            else{ temp=t; 
                  t=t->right; 
                  free(temp);
                 } 
      } 
}

The program crashes when I try to display the BST again. I guess the deleteMin function somehow deletes the entire BST.PLease help and thank you in advance

In a BST with 1,2,3 the function should delete 1(root). The problem seems to be in the else block. If I make a BST with 4,3,2,1 t is on node 1 when it reaches the else block and the program crashes on

Code:

t=t->right;

(t->right is NULL in this case).
If I make a BST with 4,3,1,2 (node 2 is the right child of node 1) t is on node 1 in the else block, it makes the assignment

Code:

t=t->right;

(t is now on node 2) and the program crashes on

Code:

free(temp);

.

The BST is not balanced, the first number entered is the root and the rest are inserted accordingly (smaller to the left, bigger to the right) so when BST is 4,3,2,1 4 is the root and every other node is the left child for it's predecessor (3 is left child of 4, 2 left child of 3 and so on). When BST is 4,3,1,2 1 is left child of 3 and 2 is right child of 1. I do a printf before free(temp); and it is on node 1, so not NULL.

Originally Posted by iMalc

Where are you setting the appropriate pointer within the node above the one being deleted to NULL?
If you don't do that then later use of the tree will likely attempt access the deleted memory.

Yes the problem was with the pointer of the node above the one being deleted. Thanks for pointing that out. So I had to check while remaining on the node above the one being deleted if the minimum one has any right child, do the connections and then delete it. If it doesn't have any children I just delete it and set the pointer of the node above to NULL. The program works with this code:

Code:

void deleteMin(struct node* t)
{
    struct node* temp;
    if(t!=NULL){
        while(t->left->left!=NULL)
            t=t->left;

        if(t->left->right!=NULL)
        {
            temp=t->left;
            t->left=t->left->right;
            free(temp);
        }else{
            free(t->left->left);
            t->left = NULL;
        }
    }
}