Back to Code List
c++

Binary Search Tree

This is an implementation of a binary search tree with several helper functions and tree display options.

   main.cpp

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

ofstream outputFile; //outputFile is defined as a global variable

struct TreeNode
{
	int key;
	TreeNode *left;				
	TreeNode *right;

	//constructor of the struct
	TreeNode (int key1, TreeNode *left1 = NULL, TreeNode *right1 = NULL)
	{
		key = key1;
		left = left1;
		right = right1;
	}
};

class BST
{
	private:
		TreeNode * root; // the root of the tree
		void destroySubTree(TreeNode *);// delete all nodes of the tree
		void displayPreOrder(TreeNode *); //function overload, pre-order traversal
		void displayInOrder(TreeNode *);//function overload, in-order traversal
		void displayPostOrder(TreeNode *); //function overload, post-order traversal

	public:
		BST() { root = NULL; }
		~BST() { destroySubTree(root); }
		void displayPreOrder() { displayPreOrder(root); }// pre-order traversal
		void displayInOrder() { displayInOrder(root); }//in-order traversal
		void displayPosteOrder() { displayPostOrder(root); }//post-order traversal
		void insert(int x);//please complete this function
		void remove(int x);//please complete this function
		bool search(int x);//please complete this function
		int findMin();//please complete this function
		TreeNode* insert(TreeNode*, int);
		void remove(TreeNode*&, int);
		TreeNode* search(TreeNode*, int);
		TreeNode* findMin(TreeNode*, int);
		int minValue(TreeNode*);
		int remove(TreeNode*);
		TreeNode* getSuccessor(TreeNode*);
};

//please complete this function: insert a new node with key x
void BST::insert(int x)
{
	//insert a new node whose key is x to the tree. If there is already a node whose
	//key is x, then we do nothing.
	if (root == NULL)
		root = insert(NULL, x);
	else
		insert(root, x);
}

TreeNode* BST::insert(TreeNode* node, int x)
{
	// base case, no root node or an empty leaf, create it
    if(node == NULL)
        return new TreeNode(x);
 
    // left side
	if(x < node->key)
    {
        if(node->left == NULL)
            node->left = new TreeNode(x);
        else
            // recurse into left node
			node->left = insert(node->left, x);
    }
	// right side
    else if (x > node->key)
    {
        if(node->right == NULL)
            node->right = new TreeNode(x);
        else
			// recurse into right node
            node->right = insert(node->right, x);
    }
	// key already exists, do nothing
	else {}
    return node;
}

//remove the node whose key is x
void BST::remove(int x)
{
	//remove the node whose key is x from the tree. If x is not in the tree, then
	//we do nothing. If the node x has two children, then use the
	//in-order successor of x to replace the node x.
	remove(root, x);
}

void BST::remove(TreeNode*& node, int x)
{
	// no node, just return
    if(node == NULL)
        return;
 
	// found node with key 
    if(node->key == x)
	{
		TreeNode* temp = node;
		if (node->left == NULL && node->right == NULL)
		{
			node = NULL;
			delete temp;
		}
		else if (node->left == NULL)
		{
			node = node->right;
			delete temp;
		}
		else if (node->right == NULL)
		{
			node = node->left;
			delete temp;
		}
		// node has two children
		else
		{
			// remove the node
			node->key = minValue(node->right);
            remove(node->right, x);
		}
	}
	else
	{
		if(x < node->key)
			remove(node->left, x);
		if(x > node->key)
			remove(node->right, x);
	}
	return;
}

int BST::minValue(TreeNode* node)
{
	if (node->left == NULL)
        return node->key;
    else
        return minValue(node->left);
}

//if x is in the tree, return true;
//otherwise return false
bool BST::search(int x)
{
	//determine whether the key x is in the tree. If yes, return "true"; otherwise
	//return "false"
	return search(root, x)!=NULL;
}

TreeNode* BST::search(TreeNode* node, int x)
{
	// base case, no root
    if(node == NULL)
        return NULL;
 
    // left side
	if(x < node->key)
    {
        if(node->left == NULL)
            return NULL;
        else
            // recurse into left node
			return search(node->left, x);
    }
	// right side
    else if (x > node->key)
    {
        if(node->right == NULL)
            return NULL;
        else
			// recurse into right node
            return search(node->right, x);
    }
	// key exists
	else {
		return node;
	}
}

//return the smallest key in the tree
int BST::findMin()
{
	//return the smallest key of the tree
	return minValue(root);
}

void BST::destroySubTree(TreeNode *v)
{
	if (v == NULL)
		return;
	else
	{
		destroySubTree(v->left);
		destroySubTree(v->right);
		delete v;
	}
}

void BST::displayPreOrder(TreeNode *v)
{
	if (v != NULL)
	{
		cout << v->key << "  ";
		outputFile << v->key << "  ";
		displayPreOrder(v->left);
		displayPreOrder(v->right);
	}
}

void BST::displayInOrder(TreeNode *v)
{
	if (v != NULL)
	{
		displayInOrder(v->left);
		cout << v->key << "  ";
		outputFile << v->key << "  ";
		displayInOrder(v->right);
	}
}

void BST::displayPostOrder(TreeNode *v)
{
	if (v != NULL)
	{
		displayPostOrder(v->left);
		displayPostOrder(v->right);
		cout << v->key << "  ";
		outputFile << v->key << "  ";
	}
}

int main()
{
	BST tree;

	string inputFileName = "input.txt"; // input file with operations 
	string outputFileName = "output.txt"; // output file

	//open files
	ifstream inputFile;
	inputFile.open(inputFileName.c_str());
	if (!inputFile)
		cout << "Error opening the input file " << endl;
	
	outputFile.open(outputFileName.c_str());
	if (!outputFile)
		cout << "Error opening the output file " << endl;

	//read operations from the input file
	string op;
	int x;
	while(inputFile >> op)
	{
		if (op == "insert")
		{
			inputFile >> x; // read the value x for insert
			tree.insert(x);
		}
		if (op == "remove")
		{
			inputFile >> x; // read the value x for remove 
			tree.remove(x);
		}
		if (op == "search")
		{
			inputFile >> x;
			if (tree.search(x) == true)
			{
				cout << "The key " << x << " is in the current tree.\n";
				outputFile << "The key " << x << " is in the current tree.\n";
			}
			else// x is not in the tree
			{
				cout << "The key " << x << " is not in the current tree.\n";
				outputFile << "The key " << x << " is not in the current tree.\n";
			}
		}
		if (op == "findMin")
		{
			cout << "The smallest key in the current tree is " << tree.findMin() << endl;
			outputFile << "The smallest key in the current tree is " << tree.findMin() << endl;
		}
	}

	//print the pre-odrder traversal to both screen and the outputfile
	cout << "The pre-order traversal list is: " << endl;
	outputFile << "The pre-order traversal list is: " << endl;
	tree.displayPreOrder();
	cout << endl;
	outputFile << endl;

	//print the in-odrder traversal to both screen and the outputfile
	cout << "The in-order traversal list is: " << endl;
	outputFile << "The in-order traversal list is: " << endl;
	tree.displayInOrder();
	cout << endl;
	outputFile << endl;

	inputFile.close();
	outputFile.close();

	return 0;
}    

   input.txt

insert 114
insert 185
insert 117
insert 168
insert 188
insert 119
insert 186
findMin
insert 173
insert 40
insert 66
remove 173
insert 107
insert 155
insert 126
insert 13
findMin
insert 23
remove 188
remove 186
insert 42
insert 180
insert 200
remove 117
search 119
insert 90
insert 70
insert 152
insert 58
insert 83
remove 83
search 117
insert 184
insert 169
insert 19
search 13
insert 167
insert 93
insert 20
insert 161
findMin    

   output.txt

The smallest key in the current tree is 114
The smallest key in the current tree is 13
The key 119 is in the current tree.
The key 117 is not in the current tree.
The key 13 is in the current tree.
The smallest key in the current tree is 13
The pre-order traversal list is: 
114  40  13  23  19  20  66  42  58  107  90  70  93  185  168  119  155  126  152  167  161  180  169  184  200  
The in-order traversal list is: 
13  19  20  23  40  42  58  66  70  90  93  107  114  119  126  152  155  161  167  168  169  180  184  185  200