#pragma once
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

template <class T>
class binarySearchTree
{
private:
	class node
	{
	public:
		T data;
		node* right;
		node* left;

		node(T x)
		{
			data = x;
			right = nullptr;
			left = nullptr;
		}
	};

	node* root;

	//inset x into tree rooted at node p
	void insert(T x, node* &p)
	{
		if (p == nullptr)
			p = new node(x);
		else
		{
			if (x < p->data)
				insert(x, p->left);
			else
				insert(x, p->right);
		}
	}

	//Print all items in tree rooted at node p
	//Pre-oder traveral
	void preOrder(node* p)
	{
		if (p == nullptr)
		{
			//ah! no nodes to print!  super easy case.
			//saving so much time because we don't need to
			//write ANY code!!!!!
		}
		else
		{
			cout << p->data << endl;
			preOrder(p->left);
			preOrder(p->right);
		}
	}

	//Print all items in tree rooted at node p
	//In-order traveral.  Run time: O(n)
	void inOrder(node* p)
	{
		if (p == nullptr)
		{
			//ah! no nodes to print!  super easy case.
			//saving so much time because we don't need to
			//write ANY code!!!!!
		}
		else
		{
			inOrder(p->left);
			cout << p->data << endl;
			inOrder(p->right);
		}
	}

	//post-order traveral
	void postOrder(node* p)
	{
		if (p == nullptr)
		{
			//ah! no nodes to print!  super easy case.
			//saving so much time because we don't need to
			//write ANY code!!!!!
		}
		else
		{
			postOrder(p->left);
			postOrder(p->right);
			cout << p->data << endl;
		}
	}

	//Return the number of leaves in the tree rooted at node p.
	int numLeaves(node* p)
	{
		if (p == nullptr)
			return 0;
		else if (p->left == nullptr && p->right == nullptr)
			return 1;
		else //recursive case
		{
			return numLeaves(p->left) + numLeaves(p->right);
		}
	}

	//Return the height of the tree rooted at node p
	int height(node* p)
	{
		if (p == nullptr)
			return -1;
		else
			return 1 + max(height(p->left), height(p->right));
	}

	//Build perfectly balanced tree from given vector
	//of sorted items.  run time: O(n)
	node* buildTree(vector<T> &A, int start, int end)
	{
		if (start > end)
			return nullptr;
		else
		{
			int mid = (start + end) / 2;
			node* babynode = new node(A[mid]);

			babynode->left = buildTree(A, start, mid - 1);
			babynode->right = buildTree(A, mid + 1, end);

			return babynode;
		}
	}

public:
	binarySearchTree()
	{
		root = nullptr;
	}

	void insert(T x)
	{
		insert(x, root);
	}

	void display()
	{
		inOrder(root);
	}

	int numLeaves()
	{
		return numLeaves(root);
	}

	int height()
	{
		return height(root);
	}

	//Use a "Breadth First Search" to print tree items
	//in a "level order".
	//Run time: numberlooops x cost of body = n x O(1) = O(n).
	void levelOrderTraversal()
	{
		queue<node*> Q;
		if (root != nullptr)
			Q.push(root);

		while (!Q.empty()) //maximum #loops: n
		{
			//get and remove first item from Q
			node* x = Q.front();
			Q.pop();

			//print front item
			cout << x->data << endl;

			//put x's children into Q
			if (x->left != nullptr)
				Q.push(x->left);
			if (x->right != nullptr)
				Q.push(x->right);

		}
	}

	void createTreeFromSortedFile(string filename)
	{
		ifstream infile(filename);
		string word;
		vector<string> wordList;

		while (infile >> word)
			wordList.push_back(word);

		root = buildTree(wordList, 0, wordList.size() - 1);
	}
};