Binary Search Tree Problem

[Rishav Paul]

#include<iostream>
using namespace std;

class btree
{
      public:
             struct node
             {
                    int data;
                    node *left;
                    node *right;
             };
             
             node *root;
             btree();
             void insert(int);
             void inorder(node*);
             void preorder(node*);
             void postorder(node*);
             node* find(node*,int,int &);
             node* maximum(node*);
             node* minimum(node*);
             node* search(node*&,int);
             void rem(int);
             
};

btree::btree()
{
              root=NULL;
}



void btree::insert(int item)
{    
     node *parent=NULL;
     node *place=search(parent,item);
     if(place==NULL)
     {
             node *temp=new node;
             temp->data=item;
             temp->left=NULL;
             temp->right=NULL;
             
             if(parent==NULL)
             root=temp;
             
             if(parent!=NULL)
             {
             if(item<parent->data)
             parent->left=temp;
             
             else parent->right=temp;
             }
     }

}    

void btree::inorder(node* temp)
{
     if(temp==NULL)
     return;
     else
     {
                   inorder(temp->left);
                   cout<<temp->data<<" ";
                   inorder(temp->right);
     }
}

void btree::preorder(node* temp)
{
     if(temp==NULL)
     return;
     else
     {
                   cout<<temp->data<<" ";
                   preorder(temp->left);
                   preorder(temp->right);
     }
}
void btree::postorder(node* temp)
{
     if(temp==NULL)
     return;
     else
     {
                   postorder(temp->left);
                   postorder(temp->right);
                   cout<<temp->data<<" ";
     }
}

btree::node* btree::maximum(node* temp)
{
             while(temp->right!=NULL)
             return maximum(temp->right);
             return temp;
}

btree::node* btree::minimum(node* temp)
{
             while(temp->left!=NULL)
             return minimum(temp->left);
             return temp;
}

btree::node* btree::search(node *&parent,int item)
{
             
             node *temp=root;
             
             while(temp!=NULL)
             {
              if(temp->data==item)
              return temp;
              
              parent=temp;
              
              if(item<temp->data)
              temp=temp->left;
              
              else temp=temp->right;
             }
             
             return NULL;
}
             
void btree::rem(int item)
{
     node *parent=NULL;
     node *temp=search(parent,item);
     
     if(temp==NULL)
     {
                   cout<<"Item does not exist\n";
                   return;
     }
     
     if(temp->left!=NULL&&temp->right!=NULL)
     {
       parent=temp;
       node *succ=temp->right;
       
       while(succ->left!=NULL)
       {
             parent=succ;
             succ=succ->left;
       }
       
       temp->data=succ->data;
       temp=succ;
     }
     
     if(temp->left==NULL&&temp->right==NULL)
     {
                 if(parent->right==temp)
                 parent->right==NULL;
                 
                 else parent->left==NULL;
                 
                 delete temp;
                 return;
     }
     
     if(temp->left==NULL&&temp->right!=NULL)
     {
                 if(parent->left==temp)
                 parent->left=temp->right;
                 
                 else parent->right=temp->right;
                 
                 delete temp;
                 return;
     }
     
     if(temp->left!=NULL&&temp->right==NULL)
     {
                 if(parent->left==temp)
                 parent->left=temp->left;
                 
                 else parent->right=temp->left;
                 
                 delete temp;
                 return;
     }    
}               
               
int main()
{
    btree a;
    
    a.insert(1);
    a.insert(3);
    a.insert(4);
    a.insert(2);
    a.insert(7);
    a.insert(6);
    a.insert(5);
    a.inorder(a.root);cout<<endl;
a.preorder(a.root);cout<<endl;a.postorder(a.root);
cout<<endl;
    cout<<a.maximum(a.root)->data;cout<<endl;
    cout<<a.minimum(a.root)->data;cout<<endl;
    a.rem(3);a.rem(7);a.rem(4);
    
    a.inorder(a.root);
    system("pause");
    return 0;
}

The program crashes. Where is the mistake?

[Rishav Paul]

I think the problem occurs when I try to delete a node with two children. Help me someone please. I cannot identify the problem.

[o1vk4iN6]

A lot of little things...

// dont need recursive here, simple problem..

btree::node* btree::maximum(node* temp)
{
// old
             while(temp->right!=NULL)
                          return maximum(temp->right);

             return temp;

// new
             if( temp == nullptr ) return nullptr;

             while( temp->right != nullptr )
                          temp = temp->right;

             return temp;
}

Same goes for minimum.

Could always debug yourself, see what function is causing the crash. If you have a debugger can also check which line is causing it.

[Rishav Paul]

Thanks Xerzi.
But the maximum and minimum functions are not causing the crash. Agreed that recursive is not required here.

The crash is caused by the inorder function, after the deletion of a node with two children occurs. Inorder works fine otherwise.

[Rishav Paul]

I get the required outputs when I do not delete any nodes. Hence, I am sure that maximum and minimum functions are working okay.

[ne555]

$ g++ -Wall foo.cpp
foo.cpp: In member function ‘void btree::rem(int)’:
foo.cpp:159:23: warning: statement has no effect [-Wunused-value]
foo.cpp:161:26: warning: statement has no effect [-Wunused-value]

[o1vk4iN6]

I know it's not the problem, I was saying you should debug it yourself. It is unreasonable to expect someone to do it for you. If I slapped 1000 lines of code on your plate and said find what's wrong, would you do it ?

[rollie]

Rishav, one of the most important skills in professional programming is the ability to debug a program. Most of the time, you will be debugging someone elses code, and not writing it from scratch. Either learn to use your debugger, or for a more simple approach, just log output in each function as a sort of sanity-check, to ensure variables are the value you expect them to be.