I am running into (pretty serious) valgrind issues as I run my application. As far as I can tell, my BST has some memory loss, to put it rather clinically. I've tried to create the right destructor on my BST<T> class, which contains BSTNode<T> nodes (both are shown below in my BST.h file). However, it still seems as though there are some major memory leaks.

To accompany this plea for another pair of eyes, I also wonder what the correct syntax is for freeing up the memory for something like:

Foo * myFoo = new Foo();

can I simply call:

delete myFoo;

in order to free up the heap memory created when

new Foo();

was called?

Thank you all in advance.

#ifndef CS240_BST_H
#define CS240_BST_H

#include <string>
#include <ostream>
#include <iostream>
#include "UnitTest.h"
#include "LinkedList.h"

template <typename T> class BSTNode;
template <class T> class BST;

using namespace std;

//!  BSTNode implements a binary search tree node
template <typename T> class BSTNode
{
	friend class BST<T>;   //!< BST can access private members of BSTNode

	public:

		//!  Constructor
		BSTNode(T * v) : value(v), left(NULL), right(NULL)
		{
		}

		//!Destructor
		~BSTNode()
		{
			delete value;
			delete left;
			delete right;
		}

		//!  Read-only public methods for use by clients of the BST class
		T * GetValue() const
		{
			return value;
		}

		BSTNode<T> * GetLeft() const
		{
			return left;
		}

		BSTNode<T> * GetRight() const
		{
		  return right;
		}

		//! Assignment operator
		BSTNode<T> & operator=(const BSTNode<T> & other)
		{
			if(this != &other)
			{
				value=other.value;
				left=other.left;
				right=other.right;
			}

			return *this;
		}

	private:
		T * value;  //!< value stored in the node
		BSTNode<T> * left;     //!< pointer to the node's left child
		BSTNode<T> * right;    //!< pointer to the node's right child
};


//!  BST implements a binary search tree
template <typename T> class BST
{

	public:
		//!  No-arg constructor.  Initializes an empty BST
		BST():root(NULL), size(0)
		{
		}

		//!  Destructor
		~BST()
		{
			Clear();
		}

		//!  Assignment operator.  Makes a complete copy of its argument
		//!  @return Reference to oneself
		BST<T> & operator =(const BST<T> & other)
		{
			if(this != &other)
			{
				Clear();
				root = CopyRecursive(other.root);
				size = other.size;
			}

			return *this;
		}

		//!  @return a pointer to the root node of the tree, or NULL if the tree is empty.
		//!  @note This is useful for BST clients that need to traverse the tree.)
		BSTNode<T> * GetRoot()const
		{
			if(size == 0)
				return NULL;
			return root;
		}


		//!  @return true if the BST is empty, or false if the BST is not empty
		bool IsEmpty() const
		{
			if(size == 0)
				return true;
			return false;
		}


		//!  Removes all values from the BST
		void Clear()
		{
			delete root;
			root = NULL;
			size = 0;
		}


		//!  @return the number of values in the BST
		int GetSize() const
		{
			if(size >= 0)
				return size;
			else
				return -1;
		}


		//!  Inserts value v into the BST
		//!
		//!  @param v The new value being inserted
		//!
		//!  @return a pointer to the newly inserted node, or NULL if v was already
		//!          in the tree (i.e., NULL is used to indicate a duplicate insertion)
		BSTNode<T> * Insert(T & v)
		{
			if(size == 0)
			{
				size++;
				return root = new BSTNode<T>(&v);
			}
			else
				return InsertRecursive(v, root);
		}

		//!  Searches the tree for value v
		//!
		//!  @param v The new value being searched for
		//!
		//!  @return a pointer to the node containing v, or NULL if v is not in the tree
		BSTNode<T> * Find(T & v)
		{
			if(size == 0)
				return NULL;
			else
				return FindRecursive(v, root);
		}


		BSTNode<T> * FindRecursive(T & valueToFind, BSTNode<T> * node_to_check)
		{
			if(valueToFind < *node_to_check->GetValue())
			{
				if(node_to_check->left == NULL)
					return NULL;
				return FindRecursive(valueToFind, node_to_check->left);
			}
			else if(valueToFind > *node_to_check->GetValue())
			{
				if(node_to_check->right == NULL)
					return NULL;
				return FindRecursive(valueToFind, node_to_check->right);
			}
			else if(valueToFind == *node_to_check->GetValue())
				return node_to_check;
		}

		LinkedList<T> * GetList()
		{
			LinkedList<T> * valueList = new LinkedList<T>();

			if(root != NULL)
				GetRecursive(valueList, root);
			else
				return NULL;

			return valueList;
		}

		void GetRecursive(LinkedList<T> * _valueList, BSTNode<T> * node)
		{
			if(node->left != NULL)
				GetRecursive(_valueList, node->left);
			if(node->right != NULL)
				GetRecursive(_valueList, node->right);
			_valueList->Insert(*node->GetValue(), NULL);
		}

		static bool Test(ostream & os)
		{
			bool success = true;

			cout << "---------TESTING BST------------" << endl;

			BST<string> test_bst;

			TEST(test_bst.GetSize() == 0);

			string test1 = "hello";
			test_bst.Insert(test1);

			string test2 = "goodbye";
			test_bst.Insert(test2);

			string test3 = "testing";
			test_bst.Insert(test3);

			string test4 = "question";
			test_bst.Insert(test4);

			string test5 = "fourth";
			test_bst.Insert(test5);

			string test6 = "next";
			test_bst.Insert(test6);


			TEST(test_bst.Find(test1));
			TEST(test_bst.Find(test2));
			TEST(test_bst.Find(test3));
			TEST(test_bst.Find(test4));
			TEST(test_bst.Find(test5));
			TEST(test_bst.Find(test6));

			//Test size after addition of 6 distinct elements
			TEST(test_bst.GetSize() == 6);

			//Add a duplicate value
			string test7 = "next";
			test_bst.Insert(test7);

			//Size should still be 6.
			TEST(test_bst.GetSize() == 6);

			LinkedList<string> * ll = test_bst.GetList();

			cout << "linked list size is " << ll->GetSize() << endl;
			cout << "first element is " << ll->Get(0) << endl;

			return success;
		}

	private:
		BSTNode<T> * root;
		int size;

		//NEED TO FIX THIS TO WORK.
		BSTNode<T> * InsertRecursive(T & valToInsert, BSTNode<T> * n)
		{
			/*
				If the sent value is less than the current node's left value,
				keep traversing. If left node does not exist, add it to the tree
			*/
			if(valToInsert < *n->value)
			{
				//If there is no value to the left, then make a new node a slap it there.
				if(n->left == NULL)
				{
					n->left = new BSTNode<T>(&valToInsert);
					size++;
					return n->left;
				}
				//If there IS a node to the left, take that node and keep going down the path.
				return InsertRecursive(valToInsert, n->left);
			}
			else if(valToInsert > *n->value)
			{
				if(n->right==NULL)
				{
					n->right = new BSTNode<T>(&valToInsert);
					size++;
					return n->right;
				}
				return InsertRecursive(valToInsert, n->right);
			}
			//Couldn't add the specified value because it was already in the tree.
			else
				return NULL;
		}


		BSTNode<T> * CopyRecursive(BSTNode<T> * node_to_recurse)
		{
			if(node_to_recurse != NULL)
			{
				BSTNode<T> * temp = new BSTNode<T>(node_to_recurse->GetValue());
				temp->left = CopyRecursive(node_to_recurse->GetLeft());
				temp->right = CopyRecursive(node_to_recurse->GetRight());
				return temp;
			}
			else
			{
				return NULL;
			}
		}
};


#endif /* CS240_BST_H_ */

Deleting the root of a tree won't free the memory allocated for the other nodes. You will lose ownership of the memory allocated by disowning the other left and right pointers.
Doing this

int* y=new int(5);
y=new int(6); //lost ownership of (new int(5))

will create a memory leak. So your Clear() function should also be recursive but you can take advantage of a traversal routine to dispose of all the dynamic allocated memory thus simplifying your work.Also the destructors and the copy assignment overloads as well as the CopyRecursive function should benefit of some attention regarding this issue.
As a note , when deleting a node you must'nt delete its siblings but hook them to the deleted node's parent node unless it's a leaf and deleting the siblings will be redundant.

First of all, yes, you are correct in that Foo * myFoo = new Foo(); must be freed with delete mFoo; .

The main problem that I see with your code is the way you handle the values stored in the nodes of your tree. Basically, the values are given to your tree (from the insertions) as non-const references, of which you take the addresses (or pointers) and store them in the nodes of the tree. Then, when you delete a node from the tree, you call delete value; and that is a big problem, because you have no control over how the value was created, you have no ownership right to delete that value.

Another related problem is that when you copy a node (either through the assignment operator or copy-constructor), you do a shallow copy of the pointers (value, left, right) which is all wrong and dangerous. When doing this, both the source node (which was copied) and the destination node (to which the source node was copied) have pointers to the same left-right nodes and to the same value object. When you delete both the source and the destination nodes, you will request the deletion of the same memory twice! Boom! Crash! You need to make a DEEP COPY, meaning not copying the pointers, but allocating new memory and copying the content pointed to by the pointers in the source node. Also, you need a copy-constructor that does that, see the Big Three, or my tutorial on RAII (a long but worthwhile read).

Also note that your assignment operator is leaking memory! You don't delete the old memory your node is already pointing to before the assignment.

The overall problem you have is a lack of protection of your class invariants. This idea of making a node class which befriends to tree class, is a dangerous game to play and you are suffering the consequences of it. Your node class is wide open (by design) and you have intentionally made its code incomplete and dangerous. I understand that most of the code that handles your nodes is part of your tree class, and that in your mind the fact that the node class itself is incomplete, dangerous and leaking all over, is mitigated by the fact that the tree class is aware of that and handles the node class correctly (it largely does indeed do that in your code). But this is literally playing with fire. This has many side-effects, such as making memory leak diagnostic difficult to do, because now, it's not just about the node class and how air-tight it is, it's about the interaction between the node and tree classes and making sure they work correctly. This is just a lot harder to deal with.

I would recommend that you remove the friendship, and that you design your node class to be air-tight, as recommended in my tutorial linked above.

Great replies. Thank you both. Really great things that I'm learning here. I do recognize now the dire situation I am in now! However, as is often the case, time constraints are making it difficult for me to really soak it all in. This BST is used throughout a webcrawling application that I am designing, and as such, it would take an especially long time to re-hash all the calls to it and such.

So I guess my question is - would it be possible to redesign my BST class without having to rehash all the calls and goings-on outside of it? I do believe it functions as far as input and output go - but when it comes to memory management, it doesn't work.

Let me rephrase this:

BSTNode<T> * Insert(T & v)
		{
			if(size == 0)
			{
				size++;
				return root = new BSTNode<T>(&v);
			}
			else
				return InsertRecursive(v, root);
		}

basically, my question is - I have to make a new instance of an object before I ever stuff it into my BST. According to this practice (if it is sane at all), do I just go about deleting the actualy INSTANCES outside of my BST somewhere, or is there some way to delete the instances that were stuffed into BST even though BST never made them?

When you insert an object you should pass it as a const reference first of all (const T&). What your function is trying to do is creating copies of v allocated dynamically where new BSTNode<T>(v) is invoking BSTNode's copy constructor. The memory should be handled internally by means of the destructors and routines designated to freeing memory associated with individual nodes or the entire tree(in a traversal). Why don't you just study some available implementation btw?

In your BSTNode<T> assignment operator you have a serious leak. And the solution is not simple unless you create a BSTNode<T> copy constructor so you can do this:

BSTNode<T> & operator=(const BSTNode<T> & other)
	{
		if(this != &other)
		{
			// First, clean up old values.
			delete value;
			delete left;
			delete right;

			// Now, assign new values.
			value = new T(*(other.value));
			left = new BSTNode<T>(*(other.left));
			right = new BSTNode<T>(*(other.right));
		}
		return *this;
	}

This is part of what Mike_2000_17 was getting at with his reference to DEEP COPY operations. You have to do the same thing for the copy constructor. I didn't look at your code beyond this, but it is indicative that although you are starting to think about how your code functions, you need to become aware of the pitfalls of just passing pointers around. Also, look into using smart pointers. They will help you simplify your code in that you can assign a pointer to one, use it like a pointer, but when it goes out of scope, it will be deleted automatically so you don't have to futz with all the delete operations that you would have to use otherwise.

>> This BST is used throughout a webcrawling application that I am designing, and as such, it would take an especially long time to re-hash all the calls to it and such.

If this is not for an assignment which specifically requires you to design your own BST, then why are you designing your own BST? Use the standard facilities already available, in this case, std::set which is a BST, or, similarly, std::map , or the hash-function versions of them std::unordered_set and std::unordered_map . Don't reinvent the wheel!

If you are looking for a production-grade implementation of a BST, then grab a production-grade implementation of a BST. The standard ones are good. If you need cache-optimized versions, you might have to look a bit further, there are plenty of solutions available out-there, for starters I have made an implementation of a B-tree and a Cache-oblivious B-tree, which can easily be used as storage for a red-black BST.


>> So I guess my question is - would it be possible to redesign my BST class without having to rehash all the calls and goings-on outside of it? I do believe it functions as far as input and output go - but when it comes to memory management, it doesn't work.

The problems you have with your implementation are about its structure. You could certainly fix it up to a working status, but it's more of a hassle and hazard than restructuring it. Also, considering that a BST is essentially just a data structure, it would seem that not getting the memory management working correctly is tantamount to not having much of anything working correctly with it. The traversal-type algorithms on your BST are pretty simple (not even self-balancing) and don't constitute a significant part of it, handling the memory and the data structure correctly is the main part, and it's faulty.

In any case, reimplementing the BST does not mean (or have to mean) changing the way it is used by outside code, much to the contrary actually. You can and should, for the most part, leave the interface of the BST class unchanged, it's what goes on under-the-hood that must change a lot.

Okay. I changed things up a bit in my entire project - and this includes my BST. I am storing actual values within my BST - it uses T's copy constructor to store them in the BST. I felt like this was a little cleaner implementation.

#ifndef CS240_BST_H
#define CS240_BST_H

#include <string>
#include <ostream>
#include <iostream>
#include "UnitTest.h"
#include "LinkedList.h"

template <typename T> class BSTNode;
template <class T> class BST;

using namespace std;

//!  BSTNode implements a binary search tree node
template <typename T> class BSTNode
{
	friend class BST<T>;   //!< BST can access private members of BSTNode

	public:
		//!  Constructor
		BSTNode(const T & v) : value(v), left(NULL), right(NULL)
		{
		}

		//!Destructor
		~BSTNode()
		{
			cout << "________________BST NODE DESTRUCTOR______________" << endl;
			delete left;
			delete right;
		}

		//!  Read-only public methods for use by clients of the BST class
		T & GetValue()
		{
			return value;
		}

		BSTNode<T> * GetLeft() const
		{
			return left;
		}

		BSTNode<T> * GetRight() const
		{
		  return right;
		}

		//! Assignment operator
		BSTNode<T> & operator=(const BSTNode<T> & other)
		{
			if(this != &other)
			{
				value=other.value;
				left=other.left;
				right=other.right;
			}
			return *this;
		}

	private:
		T value;  //!< value stored in the node
		BSTNode<T> * left;     //!< pointer to the node's left child
		BSTNode<T> * right;    //!< pointer to the node's right child
};


//!  BST implements a binary search tree
template <typename T> class BST
{

	public:
		//!  No-arg constructor.  Initializes an empty BST
		BST():root(NULL), size(0)
		{
		}

		//!  Destructor
		~BST()
		{
			cout << "________________BST DESTRUCTOR______________" << endl;
			Clear();
		}

		//!  Assignment operator.  Makes a complete copy of its argument
		//!  @return Reference to oneself
		BST<T> & operator =(const BST<T> & other)
		{
			if(this != &other)
			{
				Clear();
				root = CopyRecursive(other.root);
				size = other.size;
			}

			return *this;
		}

		//!  @return a pointer to the root node of the tree, or NULL if the tree is empty.
		//!  @note This is useful for BST clients that need to traverse the tree.)
		BSTNode<T> * GetRoot()const
		{
			if(size == 0)
				return NULL;
			return root;
		}


		//!  @return true if the BST is empty, or false if the BST is not empty
		bool IsEmpty() const
		{
			if(size == 0)
				return true;
			return false;
		}


		//!  Removes all values from the BST
		void Clear()
		{
			delete root;
			root = NULL;
			size = 0;
		}


		//!  @return the number of values in the BST
		int GetSize() const
		{
			if(size >= 0)
				return size;
			else
				return -1;
		}


		//!  Inserts value v into the BST
		//!
		//!  @param v The new value being inserted
		//!
		//!  @return a pointer to the newly inserted node, or NULL if v was already
		//!          in the tree (i.e., NULL is used to indicate a duplicate insertion)
		BSTNode<T> * Insert(const T & v)
		{
			if(size == 0)
			{
				size++;
				return root = new BSTNode<T>(v);
			}
			else
				return InsertRecursive(v, root);
		}

		//!  Searches the tree for value v
		//!
		//!  @param v The new value being searched for
		//!
		//!  @return a pointer to the node containing v, or NULL if v is not in the tree
		BSTNode<T> * Find(T & v)
		{
			cout << "FINDING 1" << endl;
			if(size == 0)
				return NULL;
			else
			{
				cout << "FINDING 2" << endl;
				return FindRecursive(v, root);
			}
		}

		BSTNode<T> * FindRecursive(T & valueToFind, BSTNode<T> * node_to_check)
		{
			cout << "FINDING 6" << endl;
			if(valueToFind < node_to_check->GetValue())
			{
				cout << "FINDING 3" << endl;
				if(node_to_check->left == NULL)
					return NULL;
				return FindRecursive(valueToFind, node_to_check->left);
			}
			else if(valueToFind > node_to_check->GetValue())
			{
				cout << "FINDING 4" << endl;
				if(node_to_check->right == NULL)
					return NULL;
				return FindRecursive(valueToFind, node_to_check->right);
			}
			else if(valueToFind == node_to_check->GetValue())
			{
				cout << "FINDING 5" << endl;
				return node_to_check;
			}
			cout << "FINDING 7" << endl;
		}

		T * FindPointerToValue(T & v)
		{
			if(size == 0)
				return NULL;
			else
			{
				BSTNode<T> * node = FindRecursive(v, root);
				return &node->value;
			}
		}

		LinkedList<T> * GetList()
		{
			LinkedList<T> * valueList = new LinkedList<T>();

			if(root != NULL)
				GetRecursive(valueList, root);
			else
				return NULL;

			return valueList;
		}

		void GetRecursive(LinkedList<T> * _valueList, BSTNode<T> * node)
		{
			if(node->left != NULL)
				GetRecursive(_valueList, node->left);
			if(node->right != NULL)
				GetRecursive(_valueList, node->right);
			_valueList->Insert(node->value, NULL);
		}

		static bool Test(ostream & os)
		{
			bool success = true;

			cout << "---------TESTING BST------------" << endl;

			BST<string> test_bst;

			TEST(test_bst.GetSize() == 0);

			string test1 = "hello";
			test_bst.Insert(test1);

			string test2 = "goodbye";
			test_bst.Insert(test2);

			string test3 = "testing";
			test_bst.Insert(test3);

			string test4 = "question";
			test_bst.Insert(test4);

			string test5 = "fourth";
			test_bst.Insert(test5);

			string test6 = "next";
			test_bst.Insert(test6);

			TEST(test_bst.Find(test1));
			TEST(test_bst.Find(test2));
			TEST(test_bst.Find(test3));
			TEST(test_bst.Find(test4));
			TEST(test_bst.Find(test5));
			TEST(test_bst.Find(test6));

			//Test size after addition of 6 distinct elements
			TEST(test_bst.GetSize() == 6);

			//Add a duplicate value
			string test7 = "next";
			test_bst.Insert(test7);

			//Size should still be 6.
			TEST(test_bst.GetSize() == 6);

			LinkedList<string> * ll = test_bst.GetList();

			cout << "linked list size is " << ll->GetSize() << endl;
			cout << "first element is " << ll->Get(0) << endl;

			delete ll;

			return success;
		}

	private:
		BSTNode<T> * root;
		int size;

		//NEED TO FIX THIS TO WORK.
		BSTNode<T> * InsertRecursive(const T & valToInsert, BSTNode<T> * n)
		{
			/*
				If the sent value is less than the current node's left value,
				keep traversing. If left node does not exist, add it to the tree
			*/
			if(valToInsert < n->value) //valToInsert < *n->value
			{
				//If there is no value to the left, then make a new node a slap it there.
				if(n->left == NULL)
				{
					n->left = new BSTNode<T>(valToInsert);
					size++;
					return n->left;
				}
				//If there IS a node to the left, take that node and keep going down the path.
				return InsertRecursive(valToInsert, n->left);
			}
			else if(valToInsert > n->value)
			{
				if(n->right==NULL)
				{
					n->right = new BSTNode<T>(valToInsert);
					size++;
					return n->right;
				}
				return InsertRecursive(valToInsert, n->right);
			}
			//Couldn't add the specified value because it was already in the tree.
			else
				return NULL;
		}


		BSTNode<T> * CopyRecursive(BSTNode<T> * node_to_recurse)
		{
			if(node_to_recurse != NULL)
			{
				BSTNode<T> * temp = new BSTNode<T>(node_to_recurse->GetValue());
				temp->left = CopyRecursive(node_to_recurse->GetLeft());
				temp->right = CopyRecursive(node_to_recurse->GetRight());
				return temp;
			}
			else
			{
				return NULL;
			}
		}
};


#endif /* CS240_BST_H_ */

However, I am still getting errors even on the Insert() and subsequent InsertRecursive() methods - I've been debugging them for hours - and just can't come up with a solution. Any ideas?

Your Insert functions seem to work as it should. I ran your code and all the unit-test passed correctly. What's the problem?

Your function to build the linked-list is not going to put the elements in sorted order, you need to do this:

void GetRecursive(LinkedList<T> * _valueList, BSTNode<T> * node)
		{
			if(node->left != NULL)
				GetRecursive(_valueList, node->left);
			_valueList->Insert(node->value, NULL);
			if(node->right != NULL)
				GetRecursive(_valueList, node->right);
		}

Notice that the inserting of the current item must go in between the left and right inserts.

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.