Binary Search Tree Implementation

Hello Experts,

I am currently learning how to implement a binary search tree using templates. As part of the learning experience, I am learning to write a program in C++ that will do the following:

1) Read in from a text file
2) Sort the words from the text file into nodes
3) Display the BST once the program finishes sorting through the text file

Below is the code I have written so far.

#include "stdafx.h"
#include <iostream>
#include <string>
#include <fstream>

template <class T>
class BST
	{
		// Internal Node Structure Class
		struct BSTNode
		{
			T data;
			BSTNode* left;		// Store address of left child node
			BSTNode* right;		// Store address of right child node

			// New Nodes
			// Node will have val assigned to data and empty child nodes
			BSTNode(T val):data(val),left(NULL),right(NULL)
				{

				}	// End Node Constructor
		};	// End Node Structure

		BSTNode* rootPtr;					// Root Node Pointer

		void display(BSTNode*);			// Declare a display method for an individual Node
		void freeMem(BSTNode*);			// Declare a method to be used in the destructor
	
	public:
		BST();							// Constructor
		~BST();							// Destructor
		void insert();					// Insert Method
		void display();					// Display Method
	};	// End BST Class Template

// BST Constructor with the root pointer set to NULL
template <class T>
BST<T>::BST():rootPtr(NULL)
	{

	}	// End BST Method Template

// BST Destructor that will free up memory and remove nodes
template <class T>
BST<T>::~BST()
	{
		freeMem(rootPtr);
	}	// End ~BST Method Template

// FreeMem Method used in the destructor
template <class T>
BST<T>::freeMem(BST::BSTNode *node)
	{
		// Do nothing if the node has nothing
		if(node == NULL)
			{
				return;
			}	// End If Statement

		// Remove the left child node
		if(node->left)
				freeMem(node->left);
		// Remove the right child node
		if(root->right)
				freeMem(node->right);
		delete node;
	}	// End FreeMem Method Template

// Insert Method
template <class T>
void BST<T>::insert()
	{
		Node* node = NULL;

		try
			{
				node = new Node(val);
			}	// End Try Block

		catch(std::bad_alloc &exception)
			{
				std::calloc << "Caught bad_alloc: " << exception.what() << std::endl;				// Display the error message
				EXIT_FAILURE;																		// Terminate the program
			}	// End Catch Block

		Node *temp = NULL;
		Node *prev = NULL;

		temp = rootPtr;		// Assign the rootPtr to temp for insertion algorithm

		// Runs while temp is not NULL
		while(temp)
			{
				prev = temp;																			// Assign temp value to prev

				// Push temp data to the right node
				if(temp->data < node->data)
					{
						temp = temp->right
					}	// End If Statement

				// Push temp data to the left node
				else
					{
						temp = temp->left;
					}	// End Else Statement
			}	// End While Loop

		// Assign the address of a node to rootPtr if there is no previous address stored
		if(prev == NULL)
			{
				rootPtr = node;
			}	// End If Statement

		else
			{
				// Push prev right child node as node value
				if(prev->data < node->data)
					{
						prev->right = node;
					}	// End If Statement

				// Push prev left child node as node value
				else
					{
						prev->left = node;
					}	// End Else Statement
			}	// End Else Statement
	}	// End Insert Method Template

// Display method for an individual node
template <class T>
void BST<T>::display(BSTNode *rootPtr)
	{
		// Display nothing if the rootPtr points to nothing
		if(rootPtr == NULL)
			{
				return;
			}	// End If Statement

		// Print out the node and its child nodes
		print(rootPtr->left);
		std::cout << rootPtr->data << std::endl;
		print(rootPtr->right);

	}	// End Node Display Method Template

// Display method for the entire BST
template <class T>
void BST<T>::display()
	{
		print(rootPtr);
	}	// End Display Method Template


int main(int argc, char argv[])
{
	std::string word;
	std::string line;
	std::ifstream declaration;
	BST <std::string> tree;

	// Read in the text file
	declaration.open("Independence.txt");

	if(declaration.is_open())
		{
			while(declaration >> word)
				{
					tree.insert();
				}	// End While Loop
		}	// End If Statement

	tree.display();

	return 0;
}

Select allOpen in new window

For the most part, I think I have a basic understanding as to how the tree will work, but I am having some problems with the coding and do not see where the problem lies. The compiler points me towards an error with an identifier in my freeMem() method. Though I have not been able to run the code for debugging until this issue is resolved, I am also having trouble figuring out if the call to insert in the main function is correct and would like some feedback. Thank you for any help you can provide.