.cpp

#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>

template <class T>
class BinTree {
private:
	struct TreeNode {
		T value;
		TreeNode *left;
		TreeNode *right;
	};

	TreeNode *root;

	//private member functions
	void insert(TreeNode *&, TreeNode*&);
	void deleteNode(T, TreeNode *&);
	void makeDeletion(TreeNode *&);
	//display functions
	void displayInOrder(TreeNode *) const;
	void displayPreOrder(TreeNode *) const;
	void displayPostOrder(TreeNode *) const;
	//count functions
	int getNodeCount(TreeNode *root);
	int getLeafCount(TreeNode *nodePtr);
	int getHeight(TreeNode *nodePtr);
	

public:
	//constructor
	BinTree(){
		root = nullptr;
	}
	//modification functions
	void insertNode(T);
	bool searchNode(T);
	void remove(T);

	//display functions
	void displayInOrder() const {
		displayInOrder(root);
	}
	void displayPreOrder() const {
		displayPreOrder(root);
	}
	void displayPostOrder() const {
		displayPostOrder(root);
	}
	
	//count functions
	int countNodes(){
		return getNodeCount(root);
	}
	int countLeafs(){
		return getLeafCount(root);
	}
	int countHeight(){
		return getHeight(root);
	}
};

//constructor
//template <class T>
//BinTree<T>(){
	//root = nullptr; }

//functions for node insertion
template <class T>
void BinTree<T>::insertNode(T num) {
	TreeNode *newNode = nullptr;
	newNode = new TreeNode;
	newNode->value = num;
	newNode->left = newNode->right = nullptr;
	insert(root, newNode);
}

template <class T>
void BinTree<T>::insert(TreeNode *&nodePtr, TreeNode *&newNode)
{
	if (nodePtr == nullptr)
		nodePtr = newNode;
	else if (newNode->value < nodePtr->value)
		insert(nodePtr->left, newNode);
	else
		insert(nodePtr->right, newNode);
}

//functions for node deletion
template <class T>
void BinTree<T>::remove(T num) {
	deleteNode(num, root);
}

template <class T>
void BinTree<T>::deleteNode(T num, TreeNode *&nodePtr) {
	if (num < nodePtr->value)
		deleteNode(num, nodePtr->left);
	else if (num > nodePtr->value)
		deleteNode(num, nodePtr->right);
	else
		makeDeletion(nodePtr);
}

template <class T>
void BinTree<T>::makeDeletion(TreeNode *& nodePtr) {
	TreeNode *tempPtr = nullptr;

	if (nodePtr == nullptr)
		std::cout << "Cannot delete an empty node";
	else if (nodePtr->right == nullptr) {
		tempPtr = nodePtr;
		nodePtr = nodePtr->left;
		delete tempPtr;
	}
	else if (nodePtr->left == nullptr) {
		tempPtr = nodePtr;
		nodePtr = nodePtr->right;
		delete tempPtr;
	}
	else {
		tempPtr = nodePtr->right;

		while (tempPtr->left)
			tempPtr = tempPtr->left;

		tempPtr->left = nodePtr->left;
		tempPtr = nodePtr;

		nodePtr = nodePtr->right;
		delete tempPtr;
	}
}

//display functions
template <class T>
void BinTree<T>::displayInOrder(TreeNode *nodePtr) const{
	if (nodePtr) {
		displayInOrder(nodePtr->left);
		std::cout << nodePtr->value << std::endl;
		displayInOrder(nodePtr->right);
	}
}

template <class T>
void BinTree<T>::displayPreOrder(TreeNode *nodePtr) const {
	if (nodePtr) {
		std::cout << nodePtr->value << std::endl;
		displayPreOrder(nodePtr->left);
		displayPreOrder(nodePtr->right);
	}
}

template <class T>
void BinTree<T>::displayPostOrder(TreeNode *nodePtr) const {
	if (nodePtr) {
		displayPostOrder(nodePtr->left);
		displayPostOrder(nodePtr->right);
		std::cout << nodePtr->value << std::endl;
	}
}

//search function
template <class T>
bool BinTree<T>::searchNode(T num) {
	TreeNode *nodePtr = root;

	while (nodePtr) {
		if (nodePtr->value == num)
			return true;
		else if (nodePtr->value > num)
			nodePtr = nodePtr->left;
		else
			nodePtr = nodePtr->right;
	}
	return false;
}

template <class T>
int BinTree<T>::getNodeCount(TreeNode *nodePtr) {
	//int nodeCount = 0;
	if (nodePtr)
		return 1 + getNodeCount(nodePtr->left) + getNodeCount(nodePtr->right);
	return 0;
}

template <class T>
int BinTree<T>::getLeafCount(TreeNode *nodePtr) {
	if (!nodePtr)
		return 0;
	if (nodePtr->left == nullptr && nodePtr->right == nullptr)
		return 1;
	else
		return getLeafCount(nodePtr->left) + getLeafCount(nodePtr->right);
}

template <class T>
int BinTree<T>::getHeight(TreeNode *nodePtr) {
	if (!nodePtr)
		return 0;
	else {
		int leftDepth = getHeight(nodePtr->left);
		int rightDepth = getHeight(nodePtr->right);
		if (leftDepth > rightDepth)
			return leftDepth + 1;
		else return rightDepth + 1;
	}
	
}
#endif // !BINARYTREE_H