Having some trouble with a Binary Search Tree

mistabob (29)
Hello,
I'm writing a binary search tree for a school project, but whenever I try to call insert(), I get an access violation. I don't know why. I have test cout statements written into insert, but none of them get triggered. Could someone explain what I'm doing wrong?

My code, BST.h:

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
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
 
#ifndef BST_H
#define BST_H

#include "Node.h"
#include <string>
#include <iostream>
#include <iomanip>

using std::ostream;
using std::istream;
using std::setw;
using std::endl;



template <typename T>
class BST
{
public:
	enum direction {left, right, none};
int counter;
Node<T>* root;
void BSTcopy(Node<T>* &copy, Node<T>* original);
void displayHelper(ostream& out, Node<T>* node, int level, direction d);
void insertHelper(Node<T> * root, Node<T>* newNode);
int heightHelper(Node<T>* base);


BST();
BST(const BST<T> &bst);
const BST<T>& operator=(const BST<T> &bst);
~BST();
void insert(T data);
T find(T key);
T remove (T key);
void display (ostream &out);
void inorderDisplay (ostream &out);
int count();
};

template <typename T>
BST<T>::BST()
{
	root = NULL;
	counter = 0;
}

template <typename T>
void BST<T>::BSTcopy(Node<T>* &copy, Node<T>* original)
{
	if(original == NULL)
	{
		copy = NULL;
	}
	else
	{
		Node<T>* copy;
		copy->data = original->data;
		BSTcopy(copy->Left, original->getLeft());
		BSTcopy(copy->Right, original->getRight());
	}
}

template <typename T>
BST<T>::BST(const BST<T> & bst)
{
	this->BSTcopy(this->root, bst.root);
	this->counter = bst.counter ;
}

template <typename T>
BST<T>::~BST()
{
	delete root;
}


template <typename T>
int BST<T>::count()
{
	return counter;
}

template <typename T>
 void BST<T>::displayHelper( ostream& out, Node<T>* node, int level, direction d)
 {
         if ( node != NULL )
         {
                 displayHelper( out, node->getLeft(), level-1, left);
                 out << endl;
                 out << setw(5*level) <<  node->getData();
                 if ( d == right )
                 out <<  "/";// << endl;
                 else if ( d == left )
                 out <<  "\\";// << endl;
                 else
                 out <<  "-";
                 out << endl;
                 displayHelper( out, node->getRight(), level-1, right);
                 out << endl;
         }
 }

 template <typename T>
 int BST<T>::heightHelper( Node<T>* base)
 {
	 int left;
	 int right;
	 if(base == T())
	 {
		 return -1;
	 }
	 left = heightHelper(base->Left);
	 right = heightHelper(base->Right);

	 if(left > right)
	 {
		 return (left + 1);
	 }
	 else
	 {
		 return (right + 1);
	 }
 }


template <typename T>
void BST<T>::display(ostream & out)
{
	displayHelper(out, this->root, heightHelper(this->root), none);
}


template <typename T>
T BST<T>::find(T key)
{
	return (root->find(key));
}



template <typename T>
void BST<T>::inorderDisplay(ostream & out)
{
	if(root == T())
	{
		return;
	}
	inorderDisplay(root.getLeft());
	root.getData();
	inorderDisplay(root.getRight());
}

template <typename T>
void BST<T>::insertHelper(Node<T> * root, Node<T>* newNode)
{
	if(newNode->data < root->data)
	{ cout << "000";
		if(root->Left == NULL)
		{
			root->Left = newNode;
			cout << "001";
			return;
		}
		else
		{ cout << "002";
		insertHelper(root->Left, newNode);
		}
	}
	else if(newNode->data > root->data)
	{cout << "003";
		if(root->Right == NULL)
		{ cout << "004";
			root->Right = newNode;
			return;
		}
		else
		{cout << "005";
			insertHelper(root->Right, newNode);
		}
	}
}



template <typename T>
void BST<T>::insert(T data)
{
	if((root->Left == NULL) && (root->Right == NULL))
	{
		root->setData(data);
		return;
	}
	 else
	{
		Node<T>* newNode;
		newNode->setData(data);
		insertHelper(this->root, newNode);
	}
	
}


template <typename T>
const BST<T>& BST<T>::operator=(const BST<T>&bst)
{
	this->BSTcopy(this->root, bst.root);
	this->counter = bst.counter ;
}


template <typename T>
T BST<T>::remove (T key)
{
	bool found = 0;
	Node<T>* curr;
	Node<T>* parent;
	curr = root;

	while(curr != NULL)
	{
		if(curr->data == key)
		{
			found = 1;
			break;
		}
		else
		{
			parent = curr;
			if(key > curr->data)
			{
				curr = curr->Right;
			}
			else
			{
				curr = curr->Left;
			}
		}
	}
	
	if(!found)
	{
		return T();
	}

	if((curr->Left == NULL && curr->Right != NULL) || (curr->Left != NULL && curr->Right == NULL))
	{
		if(curr->Left == NULL && curr->Right != NULL)
		{
			if(parent->Left == curr)
			{
				parent->Left = curr->Right;
				delete curr;
				return key;
			}
			else
			{
				parent->Right = curr->Right;
				delete curr;
				return key;
			}
		}
		else
		{
			if(parent->Left == curr)
			{
				parent->Left = curr->Left;
				delete curr;
				return key;
			}
			else
			{
				parent->Right = curr->Left;
				delete curr;
				return key;
			}
		}
	}

	if(curr->Left == NULL && curr->Right == NULL)
		{
			if(parent->Left == curr)
			{
				parent->Left = NULL;
			}
			else
			{
				parent->Right == NULL;
			}
	delete curr;
	return key;
		}


	if(curr->Left != NULL && curr->Right != NULL)
	{
		Node<T>* chkr;
		chkr = curr->Right;
		if((chkr->Left == NULL) && (chkr->Right == NULL))
		{
			curr = chkr;
			delete chkr;
			curr->Right = NULL;
		}
		else
		{
			if((curr->Right)->Left != NULL)
			{
				Node<T>* lcurr;
				Node<T>* lcurrp;
				lcurrp = curr->Right;
				lcurr = (curr->Right)->Left;
				while(lcurr->Left != NULL)
				{
					lcurrp = lcurr;
					lcurr = lcurr->Left;
				}
				curr->data = lcurr->data;
				delete lcurr;
				lcurrp->Left = NULL;
				return key;
			}
			else
			{
				Node<T>* tmp;
				tmp = curr->Right;
				curr->data = tmp->data;
				curr->Right = tmp->Right;
				delete tmp;
				return key;
			}
		}
	}

}

#endif


And here's Node.h:

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
 
#ifndef NODE_H
#define	NODE_H	


#include <iostream>
//#include "LinkedList.h"


using namespace std;

template <typename T>
class Node
{
public:
T data;
Node<T> * Left;
Node<T> * Right;
int position;
T find(T key);

	Node();
	~Node();
	Node (T newData, Node< T > *newLeft=NULL, Node<T>* newRight=NULL);
	void setData(T newdata);
	void setLeft (Node< T > *newLeft);
	void setRight (Node<T>* newRight);
	T getData ();
	Node< T > * getRight ();
	Node<T>* getLeft();

};

template <typename T>
Node<T>::Node()
{
data = T();
Left = NULL;
Right = NULL;
}

template <typename T>
Node<T>::Node(T newData, Node<T>* newLeft, Node<T>* newRight)
{
	data = newData;
	Left = newLeft;
	Right = newRight;
}

template <typename T>
T Node<T>::getData()
{
	return data;
}
template <typename T>
Node<T>* Node<T>::getLeft() 
{
	return Left;
}

template <typename T>
Node<T>* Node<T>::getRight() 
{
	return Right;
}

template <typename T>
Node<T>::~Node()
{
	delete Left;
	delete Right;
}

template <typename T>
void Node<T>::setData(T newData)
{
	data = newData;
}
template <typename T>
void Node<T>::setLeft(Node<T>* newLeft)
{
	Left = newLeft;
}

template <typename T>
void Node<T>::setRight(Node<T>* newRight)
{
	Right = newRight;
}


template <typename T>
T Node<T>::find(T key)
{
	if(this->data == key)
	{
		return key;
	}
	else if(this->Left == NULL && this->Right == NULL)
	{
		return T();
	}

	if(key > this->data)
	{
		if(this->Right == NULL)
		{
			return T();
		}
		else
		{
			this->Right->find(key);
		}
	}
	else if(key < this->data)
	{
		if(this->Left == NULL)
		{
			return T();
		}
		else
		{
			this->Left->find(key);
		}
	}
}

#endif



and finally ,here's how I'm calling insert:

1
2
3
4
5
6
7
8
9
10
 
#include "BST.h"
#include "Node.h"

void main()
{
	int first = 3;
	BST<int> test;
	test.insert(first);

}




I would very much appreciate any help! Thank you!
Peter87 (3691)
When the tree is empty root is NULL but in the insert function you assume that root is not NULL.
freddy92 (191) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
template <typename T>
void BST<T>::insert(T data)
{
	if((root->Left == NULL) && (root->Right == NULL))
	{
		root->setData(data);
		return;
	}
	 else
	{
		Node<T>* newNode;
		newNode->setData(data);
		insertHelper(this->root, newNode);
	}
	
}


You declare newNode and then immediately try to set data for it. I don't see you allocating space for it anywhere.
mistabob (29)
@Peter87,
Since it's initially NULL, am I allowed to later change root from NULL to something else? i.e, is it necessary to initialize root to NULL, since I allready include a check for if the BST is empty?

@freddy92,

I didn't think about that at all, does this fix the problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
template <typename T>
void BST<T>::insert(T data)
{
	counter++;
	if((root->Left == NULL) && (root->Right == NULL))
	{
		root->setData(data);
		return;
	}
	 else
	{
		Node<T>* newNode;
		newNode = new Node<T>*;
		newNode->setData(data);
		insertHelper(this->root, newNode);
	}
	
}
Last edited on
freddy92 (191)
Yes, I think that that fixes the problem I posted, but Peter's is still there. I think you could fix it by testing if (root == NULL) before you try anything else, and if it's true then just declare a new node, set its data to the parameter, and assign it to root.

Been a while since I worked with trees so hopefully what I'm saying is right.

Edit: actually, you didn't quite fix the problem. it needs to be newNode = new Node<T>;. I just removed the "*". You don't want a pointer to a node, you want an actual node.
Last edited on
mistabob (29)
Ok, would this fix it? I removed the check for both left and right being NULL, since that would be redundant:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
template <typename T>
void BST<T>::insert(T data)
{
	counter++;
	if(root == NULL)
	{
		Node<T>* isempty;
		isempty = new Node<T>*;
		isempty->setData(data);
		root = isempty;
	}
	 else
	{
		Node<T>* newNode;
		newNode = new Node<T>*;
		newNode->setData(data);
		insertHelper(this->root, newNode);
	}
	
}
mistabob (29)
Awesome, it did fix it! Thank you!

I moved on to find(), and find isn't working either. I insert something, and find won't... find it. Any ideas? Note: there's a find in BST and a find in Node, with the method in Node doing all the heavy lifting.


I'm also getting another NULL dereference somewhere, I'm looking for that as well.


BST find: 
1
2
3
4
5
 
template <typename T>
T BST<T>::find(T key)
{
	return (root->find(key));
}



Node find:
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
 
template <typename T>
T Node<T>::find(T key)
{
	if(this->data == key)
	{
		return key;
	}
	else if(this->Left == NULL && this->Right == NULL)
	{
		return T();
	}

	if(key > this->data)
	{
		if(this->Right == NULL)
		{
			return T();
		}
		else
		{
			this->Right->find(key);
		}
	}
	else if(key < this->data)
	{
		if(this->Left == NULL)
		{
			return T();
		}
		else
		{
			this->Left->find(key);
		}
	}
}

Last edited on
freddy92 (191)
That looks good, assuming insertHelper does what I'm thinking it does. Does it give you an error now?

Edit: woops, that was a late response to your previous post.

Edit2: Gonna repost my edit from my last post cause that still needs fixed: Edit: actually, you didn't quite fix the problem. it needs to be newNode = new Node<T>;. I just removed the "*". You don't want a pointer to a node, you want an actual node.

This would also need fixed for isempty now too. It should make sense that it needs to be new Node<T> instead of new Node <T>*, because you don't want your pointer to a Node to point to a pointer to a Node, you want it to point to an actual Node. Hope that mess of a sentence made sense.

Ok, now as for find(), you have 2 cases where nothing is being returned. I think it should be changed to this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
if(key > this->data)
	{
		if(this->Right == NULL)
		{
			return T();
		}
		else
		{
			return this->Right->find(key);
		}
	}
	else if(key < this->data)
	{
		if(this->Left == NULL)
		{
			return T();
		}
		else
		{
			return this->Left->find(key);
		}
	}


Edit again: You actually have more cases where nothing is returned. You should have an "else" at the end of your 2nd if...else if block that covers not finding the data at all (which will surely happen sometimes).
Last edited on
mistabob (29)
Yep, that was necessary;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
template <typename T>
void BST<T>::insert(T data)
{
	counter++;
	if(root == NULL)
	{
		Node<T>* isempty;
		isempty = new Node<T>;
		isempty->setData(data);
		root = isempty;
	}
	 else
	{
		Node<T>* newNode;
		newNode = new Node<T>;
		newNode->setData(data);
		insertHelper(this->root, newNode);
	}
	
}




I still have no idea about my find function though, it doesn't work at all, but the algorithm's straight from the textbook.

EDIT: saw your edits
Last edited on
freddy92 (191)
I changed your find function a bit and I think it may work now:
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
 
template <typename T>
T Node<T>::find(T key)
{
	if(this->data == key)
	{
		return key;
	}
	else if(this->Left == NULL && this->Right == NULL)
	{
		return T();
	}

	if(key > this->data)
	{
		if(this->Right == NULL)
		{
			return T();
		}
		else
		{
			return this->Right->find(key); //added return
		}
	}
	else if(key < this->data)
	{
		if(this->Left == NULL)
		{
			return T();
		}
		else
		{
			return this->Left->find(key); //added return
		}
	}
                else
                                return -1; // this will only work if the data is an int
}


OK, so without the first 2 returns I added, any recursive call to find would be pretty pointless, because whenever you got back to the one that called it, it wouldn't do anything with the found data. It needs to keep returning it until we get back to the initial caller of find().

As for the 3rd return, we need to have a case for if the data was not found at all. As I said in the comment, -1 only works as a default for ints, and only if we only want positive ones, so it isn't a very good solution. Since this tree is a template, there could be any data type in it, and you would need to return a default value for it. One solution to this would be to accept a default value as part of the constructor, then just return that if nothing was found. This gives the client the power of deciding what will be returned when nothing is found, so they will know how to check for that. Edit: Is that what return T(); is? If so that's pretty convenient, and I didn't know you could do it that way.
Last edited on
mistabob (29)
Ok,

wouldn't your code work if, instead of returning a -1, return a default type, like you said? in other words:

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
 
template <typename T>
T Node<T>::find(T key)
{
	if(this->data == key)
	{
		return key;
	}
	else if(this->Left == NULL && this->Right == NULL)
	{
		return T();
	}

	if(key > this->data)
	{
		if(this->Right == NULL)
		{
			return T();
		}
		else
		{
			return this->Right->find(key); //added return
		}
	}
	else if(key < this->data)
	{
		if(this->Left == NULL)
		{
			return T();
		}
		else
		{
			return this->Left->find(key); //added return
		}
	}
                else
                                return T(); // default T value
}





EDIT: wait, the case where the data isn't found is allready covered. Each time it returns a T() is when it reaches the end of the relevant sub tree and encounters a NULL pointer, i.e. nothing more to search through.
Last edited on
freddy92 (191)
Yeah, I had no idea you could use T(); like that. When we did stuff like this in my class a few years ago, we never did that. Does that actually work? What gets returned?

Edit in response to your edit: that may be the case, but many compilers will be angry if there's a possible way for it to get through the function without finding a return. Since your last if...else if doesn't have an else, it's gonna get pretty sad about that and probably give you an error.
Last edited on
mistabob (29)
To be honest I'm not sure, one of the reasons I'm having trouble in my own class is we get told to do stuff like this without any explanation. That, and online submission, which is literally the opposite of the bee's knees.

Speaking of which, I don't suppose you see another NULL pointer de-reference anywhere? Because Web-Cat does....
freddy92 (191)
I don't have any more time now, but I threw your code into codepad and have been testing it there; here's the current error it's finding: http://codepad.org/PfZnrXoA. It again is reaching the end of a function without returning anything. You need to make sure you will return something in ALL cases, even if logically it is covered. Once you fix that it should point out your null pointer problem, which I think is in remove. If not, keep trying your other functions until it gives you errors.
mistabob (29)
Hey, thanks so much!
mistabob (29)
So it looks like my final problem is in remove(). I'm not reattaching the nodes above the node I remove properly. Here's the code:

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
 
template <typename T>
T BST<T>::remove (T key)
{
	counter--;
	bool found = 0;
	Node<T>* curr;
	Node<T>* parent;
	curr = root;

	while(curr != NULL)
	{
		if(curr->data == key)
		{
			found = 1;
			break;
		}
		else
		{
			parent = curr;
			if(key > curr->data)
			{
				curr = curr->Right;
			}
			else
			{
				curr = curr->Left;
			}
		}
	}
	
	if(!found)
	{
		return T();
	}

	if((curr->Left == NULL && curr->Right != NULL) || (curr->Left != NULL && curr->Right == NULL))
	{
		if(curr->Left == NULL && curr->Right != NULL)
		{
			if(parent->Left == curr)
			{
				parent->Left = curr->Right;
				delete curr;
				return key;
			}
			else
			{
				parent->Right = curr->Right;
				delete curr;
				return key;
			}
		}
		else
		{
			if(parent->Left == curr)
			{
				parent->Left = curr->Left;
				delete curr;
				return key;
			}
			else
			{
				parent->Right = curr->Left;
				delete curr;
				return key;
			}
		}
	}

	if(curr->Left == NULL && curr->Right == NULL)
		{
			if(parent->Left == curr)
			{
				parent->Left = NULL;
			}
			else
			{
				parent->Right == NULL;
			}
	delete curr;
	return key;
		}


	if(curr->Left != NULL && curr->Right != NULL)
	{
		Node<T>* chkr;
		chkr = curr->Right;
		if((chkr->Left == NULL) && (chkr->Right == NULL))
		{
			curr = chkr;
			delete chkr;
			curr->Right = NULL;
		}
		else
		{
			if((curr->Right)->Left != NULL)
			{
				Node<T>* lcurr;
				Node<T>* lcurrp;
				lcurrp = curr->Right;
				lcurr = (curr->Right)->Left;
				while(lcurr->Left != NULL)
				{
					lcurrp = lcurr;
					lcurr = lcurr->Left;
				}
				curr->data = lcurr->data;
				delete lcurr;
				lcurrp->Left = NULL;
				return key;
			}
			else
			{
				Node<T>* tmp;
				tmp = curr->Right;
				curr->data = tmp->data;
				curr->Right = tmp->Right;
				delete tmp;
				return key;
			}
		}
	}
Registered users can post here. Sign in or register to post.

C++

Forum