Having some trouble with a Binary Search Tree

[mistabob]

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:

#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:

#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:

#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]

When the tree is empty root is NULL but in the insert function you assume that root is not NULL.

[freddy92]

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]

@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:

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

[freddy92]

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.

[mistabob]

Ok, would this fix it? I removed the check for both left and right being NULL, since that would be redundant:

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]

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:

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

Node find:

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

[freddy92]

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:

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).

[mistabob]

Yep, that was necessary;

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

[freddy92]

I changed your find function a bit and I think it may work now:

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.

[mistabob]

Ok,

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

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.

[freddy92]

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.

[mistabob]

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]

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]

Hey, thanks so much!

[mistabob]

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:

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