#pragma once
#include <iostream>
#include <string>
using namespace std;

class node
{
public:
	string data;
	node* left;
	node* right;

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


class binarySearchTree
{
private:
	//variables:
	node* root;

	//helper methods
	
	//Print all items in tree rooted at p
	void recDisplay(node* p)
	{
		if (p == nullptr) //base case
		{
			//do nothing, no items to print
		}
		else //recursive case
		{
			recDisplay(p->left);
			cout << p->data << endl;
			recDisplay(p->right);
		}
	}

public:
	binarySearchTree()
	{
		root = nullptr;
	}

	void insert(string x)
	{
		bool inserted = false;

		//Check if tree is empty
		if (root == nullptr)
		{
			root = new node(x);
			inserted = true;
		}

		//Otherwise, travel down tree until nullptr found
		node* current = root;
		while (! inserted)
		{

			if (x < current->data)
			{
				//go left
				if (current->left == nullptr)
				{
					//add item!
					current->left = new node(x);
					inserted = true;
				}
				else
				{
					//move current to left
					current = current->left;
				}
			}
			else
			{
				//go right
				if (current->right == nullptr)
				{
					current->right = new node(x);
					inserted = true;
				}
				else
				{
					current = current->right;
				}
			}
		}
	}

	void display()
	{
		recDisplay(root);
	}
};