Binary search tree removal

[skeet123]

I am having trouble coming up with code for removing a node in a binary search tree. This is what I have so far:

void remove(int n)
    {
         node *current=root;
         node *gptr;
        while(current != NULL){
            if(n<current->key){
                gptr=current;
                current=current->left;
            }else if(n>current->key){
                gptr=current;
                current=current->right;
            }else if(n==current->key){
                if(gptr->right->key==n){
                cout<<"1st ==key = "<<gptr->key<<endl;
                cout<<"1st ==current = "<<current->key<<endl;
                delete current;
                gptr->right=NULL;
                }else if(gptr->left->key==n){
                cout<<"1st ==key = "<<gptr->key<<endl;
                cout<<"1st ==current = "<<current->key<<endl;
                delete current;
                gptr->left=NULL;
                }

            }
        }

    }

The problem I am having is lets say for example I enter
10 8 12 11 15
If I remove the 15 it works fine. When I go back and try to remove the 11 after I remove the fifteen it gives me a segmentation fault. Any help would be appreciated.

[Chainsaw]

Because gptr->right or gptr->left could be NULL, so when you dereference it, you'll crash.

Do your nodes have a parent node or only left and right child nodes?

You could say if (gptr->right == current) gptr->right = NULL, and that way you don't have to check the key value, just the node pointer.

[skeet123]

I have a root node.Here is the entire code:

#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

class node
{
  public:
    int key;
    string value;
    node *left;
    node *right;

    node(int k, string v)
    {
        key = k;
        value = v;
        left = NULL;
        right = NULL;
    }
};
class bst
{
  private:
    node *root;

  public:
   bst()
   {
       root = NULL;
   }

    void put(int key, string value)
    {
        node *newp = new node(key,value);
        if(root != NULL)
            put(key, value, root);
        else
        {
            root=newp;
        }

    }
    void put(int key, string value, node *tmp)
    {
 node *newp = new node(key,value);
        if(key<tmp->key)
        {
            if(tmp->left != NULL)
                put(key,value,tmp->left);
            else
            {
                tmp->left=newp;
            }
        }
        else if(key>tmp->key)
        {
            if(tmp->right != NULL)
                put(key,value,tmp->right);
            else
            {
                tmp->right=newp;
            }
        }

    }
    string non_recursive_get(int n)
  {
        node *gptr=root;
        while(gptr != NULL){
            if(n<gptr->key){
                gptr=gptr->left;
            }else if(n>gptr->key){
                gptr=gptr->right;
            }else if(n==gptr->key){
                return gptr->value;
            }else{
                return "no node";
            }
        }

    }
    string recursive_get(int n)
    {
        recursive_get(n,root);
        return recursive_get(n,root);
    }
    string recursive_get(int n, node *tmp)

    {
        if(tmp!=NULL){

            if(n==tmp->key){
                return tmp->value;
            }
            else if(n<tmp->key){
                return recursive_get(n,tmp->left);
            }else if(n>tmp->key){
                return recursive_get(n, tmp->right);
            }
        }else if(tmp==NULL){
            cout<<"NO NODES IN TREE"<<endl;
        }

    }
    void remove(int n)
    {
         node *current=root;
         node *gptr;
        while(current != NULL){
            if(n<current->key){
                gptr=current;
                current=current->left;
            }else if(n>current->key){
                gptr=current;
                current=current->right;
            }else if(n==current->key){
                if(gptr->right->key==n){
                cout<<"1st ==key = "<<gptr->key<<endl;
                cout<<"1st ==current = "<<current->key<<endl;
                delete current;
                gptr->right=NULL;
                }else if(gptr->left->key==n){
                cout<<"1st ==key = "<<gptr->key<<endl;
                cout<<"1st ==current = "<<current->key<<endl;
                delete current;
                gptr->left=NULL;
                }

            }
        }

    }
};

int main(void)
{
    bst mybst;
    string cmd;
    int k;
    string v;

    while (true) {
        cin >> cmd >> k >> v;

        cout << "MAIN: cmd= " << cmd << ", key= " << k << ", v= " << v << endl;

        if (cmd == "put") {
            mybst.put(k, v);
        }else if (cmd == "dump") {     // traverse tree in ascending order
            mybst.dump();
        }else if (cmd == "dump_rev") { // traverse tree in descending order
            mybst.dump_rev();
        } else if (cmd == "get") {
            cout << "MAIN: get returns: " << mybst.non_recursive_get(k) << endl;
        } else if (cmd == "rget") {
     cout << "MAIN: rget returns: " << mybst.recursive_get(k) << endl;
        } else if (cmd == "rem") {
            mybst.remove(k);
        } else if (cmd == "quit") {
            exit(0);
        }
    }
}

[Chainsaw]

ok, so you need to fix those pointers at the least. Thanks for the readable code!

[skeet123]

ok, so you need to fix those pointers at the least. Thanks for the readable code!

Thanks for the reply I finally got it to work. Now th problem I am having is tring to remove a node with two children. Any suggestions.

[Narue]

To remove a node with two children you need to find the inorder successor or predecessor to replace it with, then reduce to the case of removing the successor or predecessor. A fairly thorough tutorial on binary search trees can be found here .