delete minimum in BST problem

This is a discussion on delete minimum in BST problem within the C Programming forums, part of the General Programming Boards category; Code: struct node { int data; struct node* left; struct node* right; }; in main i create struct node* root, ...

  1. #1
    Registered User
    Join Date
    Feb 2013
    Posts
    4

    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

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    Let's say you have a BST with nodes 1,2,3. Which node will your function delete?
    Also, check where the pointer t is when the function terminates. Check this by checking the next line of where the function is been invoked of the main.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  3. #3
    Registered User
    Join Date
    Feb 2013
    Posts
    4
    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);
    .

  4. #4
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    Quote Originally Posted by Sergiu Nistor View Post
    In a BST with 1,2,3 the function should delete 1(root).
    Shouldn't 2 be the root, 1 the left child and 3 the right child?

    It probably crashes because temp is NULL
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  5. #5
    Registered User
    Join Date
    Feb 2013
    Posts
    4
    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.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,307
    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.
    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"

  7. #7
    Registered User
    Join Date
    Feb 2013
    Posts
    4

    Solved

    Quote Originally Posted by iMalc View Post
    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;
            }
        }
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Minimum/maximum number problem. Please help!
    By PYROMANIAC702 in forum C Programming
    Replies: 43
    Last Post: 07-15-2011, 12:28 AM
  2. Finding minimum, problem with input
    By theMaze in forum C Programming
    Replies: 5
    Last Post: 03-02-2011, 12:17 PM
  3. Vector Delete Problem
    By tarheelfan_08 in forum C++ Programming
    Replies: 1
    Last Post: 04-18-2010, 01:05 AM
  4. Problem with Delete
    By Grins2Pain in forum C++ Programming
    Replies: 8
    Last Post: 09-26-2003, 09:51 AM
  5. delete[] problem
    By XSquared in forum C++ Programming
    Replies: 2
    Last Post: 10-05-2002, 03:29 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21