Binary Search Tree Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#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?
Last edited on
I think the problem occurs when I try to delete a node with two children. Help me someone please. I cannot identify the problem.
closed account (o1vk4iN6)
A lot of little things...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 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.
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.
Last edited on
I get the required outputs when I do not delete any nodes. Hence, I am sure that maximum and minimum functions are working okay.
$ 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]
closed account (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 ?
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.
Topic archived. No new replies allowed.