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

class binarySearchTree
{
private:
	class node
	{
	public:
		double data;
		node* left;
		node* right;

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

	node* root;

	void recInsert(node* &p, double x)
	{
		if (p == nullptr)
			p = new node(x);
		else if (x < p->data)
			recInsert(p->left, x);
		else
			recInsert(p->right, x);
	}

	//print all items in tree rooted
	//at node p
	//in-order traversal
	void recDisplay(node* p)
	{
		if (p == nullptr) //base case
		{
			//do nothing! no items to print!!!
			//saveing so much programming time!!!
		}
		else //recursive case
		{
			recDisplay(p->left);
			cout << p->data << endl;
			recDisplay(p->right);
		}
	}

	node* makeTree(vector<double>& A, int start, int end)
	{
		if (start > end)
			return nullptr;
		else
		{
			int mid = (start + end) / 2;
			node* p = new node(A[mid]);

			p->left = makeTree(A, start, mid - 1);
			p->right = makeTree(A, mid + 1, end);

			return p;
		}
	}

public:
	binarySearchTree()
	{
		root = nullptr;
	}

	//create a bst from a given sorted vector
	binarySearchTree(vector<double> A)
	{
		root = makeTree(A, 0, A.size() - 1);
	}

	void insert(double x)
	{
		recInsert(root, x);
	}

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