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

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

		int height;

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

	node* root;


	int height(node* p)
	{
		if (p == nullptr)
			return -1;
		else
			return p->height;
	}

	void updateHeight(node* p)
	{
		p->height= 1 + max(height(p->left), height(p->right));
	}

	//insert x into tree rooted at
	//node p.
	void recInsert(node*& p, double x)
	{
		if (p == nullptr) //base case
		{
			p = new node(x);
		}
		else //recursive case
		{
			if (x < p->data)
				recInsert(p->left, x);
			else
				recInsert(p->right, x);

			//p's height is SUS
			updateHeight(p);
		}
	}

	//print all items in tree rooted at node p
	void recDisplay(node* p)
	{
		if (p == nullptr) //base case
		{
			//don't do anything
		}
		else
		{
			recDisplay(p->left);
			cout << p->data << endl;
			recDisplay(p->right);
		}
	}

	//return number of items in tree
	//rooted at p.
	int numItems(node* p)
	{
		if (p == nullptr) //base case
			return 0;
		else //recurisive case
		{
			int numLeft = numItems(p->left);
			int numRight = numItems(p->right);
			return 1 + numLeft + numRight;
		}
	}

public:
	avlTree()
	{
		root = nullptr;
	}

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

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

	void print()
	{
		recDisplay(root);
	}

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