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


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

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

	//Insert x into the tree rooted at node p.
	void insert(node* &p, double x)
	{
		if (p == nullptr)//tree is empty)
			p = new node(x);
		else
		{
			if (x < p->data)
			{
				//insert to the left
				insert(p->left,x);//the left tree)
			}
			else
			{
				//insert to the right
				insert(p->right, x);
			}
		}
	}

	node* root;

	//print all items in tree rooted at node p.
	//In-order traversal
	void display(node* p)
	{
		if (p == nullptr)
		{
			//don't do anything, no nodes
		}
		else
		{
			display(p->left);
			cout << p->data << endl;
			display(p->right);
		}
	}

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

public:

	binarySearchTree()
	{
		root = nullptr;
	}

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

	void display()
	{
		display(root);
	}

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