BinaryTreeLinkedList.h

#pragma once
#include<vector>
#include<queue>
#include<stack>
#include "BinaryTreeADT.h"
using namespace std;
template<typename T>
struct Node
{
	Node<T> *left,*right;
	T val;
	Node(T val):left(NULL),right(NULL),val(val){}
};
template<typename T>
class BinaryTreeLinkedList:BinaryTreeADT<T>
{

	Node<T>* root;
	void  removeNode(Node<T>* &p);
	void  inorder(Node<T>* r)const;
	void  preorder(Node<T>* r)const;
	void  postorder(Node<T>* r)const;
	void  insertRec(T item,Node<T>*& root);
	bool  searchRec(T item,Node<T>* root);
	Node<T>*  findMin(Node<T> *t);
	void  bstHelper(Node<T>* root,vector<T> &v );
	Node<T>*  findMax(Node<T> *t);
	bool  isSorted(const vector<T>& v);
	void  removeRec(T item,Node<T>*& t);
	void  copyTree(Node<T>*& copiedTree,Node<T>* othertree);
	void  destroy(Node<T>*& r);
	void  destroy();
	void  linkedListToArray(Node<T>* r,vector<T> &v);
public:
	BinaryTreeLinkedList():root(NULL){}
	void insert(T item);
	void remove(int item);
	void search(T toFind);
	void insertRec(T item);
	void searchRec(T item);
	void removeRec(T item);
	void inOrder() const;
	void preOrder() const;
	void postOrder()const;
	bool isBst();
	void levelOrder();
	BinaryTreeLinkedList(const BinaryTreeLinkedList<T>& other);
	const BinaryTreeLinkedList& operator=(const BinaryTreeLinkedList<T>& other);
	~BinaryTreeLinkedList();
	friend bool operator==(BinaryTreeLinkedList<T>& T1,BinaryTreeLinkedList<T>& T2);
	vector<T> linkedListToArray();
	void arrayToLinkedList();
};

BinaryTreeADT.h

#pragma once
#include<vector>
template<typename T>
class BinaryTreeADT
{
public:
	virtual void insert(T item)=0;
	virtual void remove(T item)=0;
	virtual void search(T item)=0;
	virtual void insertRec(T item)=0;
	virtual void removeRec(T item)=0;
	virtual bool isBst()=0;
	virtual void preOrder()const=0;
	virtual void postOrder()const=0;
	virtual void inOrder()const=0;
	virtual void levelOrder()=0;
	virtual std::vector<T> linkedListToArray()=0;
	virtual void arrayToLinkedList()=0;
};

BinaryTreeLinkedList.cpp

#include "BinaryTreeLinkedList.h"
template<typename T>
void BinaryTreeLinkedList<T>::removeNode(Node<T>* &p)
{
	Node<T> *current,*trailing,*temp;
	if(p==NULL) cerr << "Can not remove from empty tree (1)"<<endl;
	else if(p->left == NULL && p->right==NULL){
		temp = p;
		p=NULL;
		delete temp;
	}
	else if(p->left==NULL){
		temp = p;
		p = p->right;
		delete temp;
	}
	else if(p->right==NULL){
		temp = p;
		p = p->left;
		delete temp;
	}
	else {
		current = p->left;
		trailing = NULL;
		while (current->right != NULL)
		{
			trailing=current;
			current = current->right;
		}
		p->val = current->val;
		if(trailing==NULL)
			p->left = current->left;
		else
			trailing->right = current->left;
		delete current;
	}
}
template<typename T>
void BinaryTreeLinkedList<T>::inorder(Node<T>* r)const
{
	if(r==NULL) return;
	else
	{
		inorder(r->left);
		cout << r->val<<endl;
		inorder(r->right);
	}
}
template<typename T>
void BinaryTreeLinkedList<T>::preorder(Node<T>* r)const
{
	if(r==NULL) return;
	else
	{
		cout << r->val<<endl;
		preorder(r->left);
		preorder(r->right);
	}
}
template<typename T>
void BinaryTreeLinkedList<T>::postorder(Node<T>* r)const
{
	if(r==NULL) return;
	else
	{
		postorder(r->left);
		postorder(r->right);
		cout << r->val<<endl;
	}
}
template<typename T>
void BinaryTreeLinkedList<T>::insertRec(T item,Node<T>*& root)
{
	if(root==NULL)
		root = new Node<T>(item);
	else if( item < root->val)
		insertRec(item,root->left);
	else
		insertRec(item,root->right);
}
template<typename T>
bool BinaryTreeLinkedList<T>::searchRec(T item,Node<T>* root)
{
	if(root==NULL)
		return false;
	if(root->val == item)
		return true;
	else if(item < root->val)
		return searchRec(item,root->left);
	else
		return searchRec(item,root->right);
	return false;
}
template<typename T>
Node<T>* BinaryTreeLinkedList<T>::findMin(Node<T> *t)
{
	if(t==NULL)
		return NULL;
	if(t->left==NULL)
		return t;
	return findMin(t->left);
}
template<typename T>
void BinaryTreeLinkedList<T>::bstHelper(Node<T>* root,vector<T> &v )
{
	if(root==NULL)
		return;
	else
	{
		bstHelper(root->left,v);
		v.push_back(root->val);
		bstHelper(root->right,v);
	}
}
template<typename T>
Node<T>* BinaryTreeLinkedList<T>::findMax(Node<T> *t)
{
	if(t==NULL)
		return;
	if(t->right==NULL)
		return t;
	return findMax(t->right);
}
template<typename T>
bool BinaryTreeLinkedList<T>::isSorted(const vector<T>& v)
{
	for(unsigned int i=0;i<v.size()-1;i++)
		if(v.at(i) <= v.at(i+1))
			continue;
		else
			return false;
	return true;
}
template<typename T>
void BinaryTreeLinkedList<T>::removeRec(T item,Node<T>*& t)
{
	if(t==NULL)
		return;
	if(item < t->val)
		removeRec(item,t->left);
	else if(item > t->val)
		removeRec(item,t->right);
	else if(t->left!=NULL && t->right!=NULL)
	{
		t->val = findMin(t->right)->val;
		removeRec(t->val,t->right);
	}
	else
	{
		Node<T>* old = t;
		t = (t->left !=NULL)?t->left:t->right;
		delete old;
	}
}
template<typename T>
void BinaryTreeLinkedList<T>::copyTree(Node<T>*& copiedTree,Node<T>* othertree)
{
	if(othertree==NULL)
		copiedTree=NULL;
	else
	{
		copiedTree = new Node<T>(othertree->val);
		copyTree(copiedTree->left, othertree->left);
		copyTree(copiedTree->right, othertree->right);
	}
}
template<typename T>
void BinaryTreeLinkedList<T>::destroy(Node<T>*& r)
{
	if(r!=NULL)
	{
		destroy(r->left);
		destroy(r->right);
		delete r;
		r=NULL;
	}
}
template<typename T>
void BinaryTreeLinkedList<T>::destroy()
{
	destroy(root);
}
template<typename T>
void BinaryTreeLinkedList<T>::linkedListToArray(Node<T>* r,vector<T> &v)
{
	if(!r)
		return;
	queue<Node<T>* > q;
	q.push(root);
	while(!q.empty())
	{
		Node<T>* temp = q.front();
		q.pop();
		v.push_back(temp->val);
		if(temp->left!=NULL)
			q.push(temp->left);
		if(temp->right!=NULL)
			q.push(temp->right);
	}
}
template<typename T>
void BinaryTreeLinkedList<T>::insert(T item)
{
	Node<T>*  current;
	Node<T>*  trailing;
	Node<T>* data = new Node<T>(item);
	if(root==NULL)
		root = data;
	else
	{
		current = root;
		while (current!=NULL)
		{
			trailing=current;
			if(item < current->val)
			{
				current = current->left;
			}
			else
			{
				current = current->right;
			}
		}
		if(item < trailing->val)
			trailing->left = data;
		else
			trailing->right = data;
	}
}
template<typename T>
void BinaryTreeLinkedList<T>::remove(int item)
{
	Node<T>* current,*trailCurrent;
	bool found = false;
	if(root == NULL) cout << "Tree is Empty!!"<<endl;
	else {
		current=root;
		while(current != NULL && !found){
			if(current->val == item)
				found = true;
			else {
				trailCurrent=current;
				if(item < current->val)
					current = current->left;
				else
					current = current->right;
			}
		}
		if(current==NULL)
			cout << "Node to be deleted is not in tree"<<endl;
		else if(found)
		{
			if(current==root)
				removeNode(root);
			else if(item < trailCurrent->val)
				removeNode(trailCurrent->left);
			else removeNode(trailCurrent->right);
		}
	}//else block ends
}
template<typename T>
void BinaryTreeLinkedList<T>:: search(T toFind)
{
	if(root==NULL)
		cout << "Can not search empty tree"<<endl;
	else
	{
		Node<T> *ptr = root;
		bool found = false;
		while (ptr!=NULL && !found)
		{
			if(toFind == ptr->val)
			{
				found=true;
			}
			if(toFind < ptr->val)
			{
				ptr = ptr->left;
			}
			else
			{
				ptr = ptr->right;
			}
		}
		if(!found)
			cout << "Vale not found"<<endl;
		else
			cout << "Found"<<endl;
	}
}
template<typename T>
void BinaryTreeLinkedList<T>:: insertRec(T item)
{
	insertRec(item,root);
}
template<typename T>
void BinaryTreeLinkedList<T>:: searchRec(T item)
{
	if(root==NULL) 
		cout << "Can not search empty tree"<<endl;
	else if(searchRec(item,root)) cout << "Found"<<endl;
	else cout << "Value does not exists"<<endl;
}
template<typename T>
void BinaryTreeLinkedList<T>::removeRec(T item)
{
	removeRec(item,root);
}
template<typename T>
void BinaryTreeLinkedList<T>::inOrder() const
{
	inorder(root);
}
template<typename T>
void BinaryTreeLinkedList<T>::preOrder() const
{
	preorder(root);
}
template<typename T>
void BinaryTreeLinkedList<T>::postOrder()const
{
	postorder(root);
}
template<typename T>
bool BinaryTreeLinkedList<T>::isBst()
{
	if(root==NULL)
		return true;
	vector<T> vec;
	bstHelper(root,vec);
	if(isSorted(vec))
		return true;
	return false;
}
template<typename T>
void BinaryTreeLinkedList<T>::levelOrder()
{
	queue<Node<T>* > q;
	q.push(root);
	while(!q.empty())
	{
		Node<T>* temp = q.front();
		q.pop();
		cout << temp->val<<endl;
		if(temp->left!=NULL)
			q.push(temp->left);
		if(temp->right!=NULL)
			q.push(temp->right);
	}
}
template<typename T>
BinaryTreeLinkedList<T>::BinaryTreeLinkedList(const BinaryTreeLinkedList<T>& other) //Copy Constructor
{

	if(other.root==NULL)
		root=NULL;
	else
		copyTree(root,other.root);
}
template<typename T>
const BinaryTreeLinkedList<T>& BinaryTreeLinkedList<T>::operator=(const BinaryTreeLinkedList<T>& other)//Assignement Operator
{

	if(this!=&other)
	{
		if(root!=NULL)
			destroy(root);
		if(other.root==NULL)
			root=NULL;
		else
			copyTree(root,other.root);
	}
	return *this;
}
template<typename T>
BinaryTreeLinkedList<T>::~BinaryTreeLinkedList()
{
	destroy(root);
}
template<typename T>
bool operator==(BinaryTreeLinkedList<T>& T1,BinaryTreeLinkedList<T>& T2)
{
	vector<T> v1;
	T1.bstHelper(T1.root,v1);
	vector<T> v2;
	T2.bstHelper(T2.root,v2);
	if(v1.size()!=v2.size())
		return false;
	for(int i=0;i<v1.size();i++)
		if(v1.at(i)!=v2.at(i))
			return false;
	return true;
}
template<typename T>
vector<T> BinaryTreeLinkedList<T>::linkedListToArray()
{
	vector<T> v;
	linkedListToArray(root,v);
	return v;
}
template<typename T>
void BinaryTreeLinkedList<T>::arrayToLinkedList()
{
	cout << "Not implemented"<<endl;
}

source.cpp

#include<iostream>
#include"BinaryTreeLinkedList.h"
using namespace std;
void main()
{
	BinaryTreeLinkedList<int> bst;
	/*bst.insertRec(80);
	bst.insertRec(200);
	bst.insertRec(300);
	bst.insertRec(150);
	bst.insertRec(70);
	bst.insertRec(90);
	bst.insertRec(60);
*/
	bool exit = false;
	do
	{
		int val;
		cout << "Enter a Val: ";cin>>val;
		cout <<"*******Insertion*******"<<endl;
		cout << "1  To Add New    Node     (Iteratively)"<<endl;
		cout << "2  To Add New    Node     (Recursively)"<<endl;
		cout <<"*******Searching*******"<<endl;
		cout << "3  To Search for Node     (Iteratively)"<<endl;
		cout << "4  To Search for Node     (Recursively)"<<endl;
		cout <<"*******Removal*********"<<endl;
		cout << "5  To Remove     Node     (Iteratively)"<<endl;
		cout << "6  To Remove     Node     (Recursively)"<<endl;
		cout <<"*******Transversal*****"<<endl;
		cout << "7  In    Order            (Recursively)"<<endl;
		cout << "8  Pre   Order            (Recursively)"<<endl;
		cout << "9  Post  Order            (Recursively)"<<endl;
		cout << "10 Level Order            (Recursively)"<<endl;
		cout << "=========================="<<endl;
		int option;cin>>option;
		cout << "=========================="<<endl;
		switch (option)
		{
		case 1:
			bst.insert(val);
			break;
		case 2:
			bst.insertRec(val);
			break;
		case 3:
			bst.search(val);
			break;
		case 4:
			bst.searchRec(val);
			break;
		case 5:
			bst.remove(val);
			break;
		case 6:
			bst.removeRec(val);
			break;
		case 7:
			bst.inOrder();
			break;
		case 8:
			bst.preOrder();
			break;
		case 9:
			bst.postOrder();
			break;
		case 10:
			bst.levelOrder();
			break;
		default:
			exit=true;
			break;
		}

	} while (!exit);


	/*bst.insert(80);
	bst.insert(200);
	bst.insert(300);
	bst.insert(150);
	bst.insert(70);
	bst.insert(90);
	bst.insert(60);*/
	/*bst.levelOrder();
	vector<int> v;
	v = bst.linkedListToArray();
	for (int i = 0; i < v.size(); i++)
	{
	cout << v.at(i)<< ' ';
	}*/

}