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.

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.

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);
        }
    }
}

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

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.

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.