// HEADER FILE
#pragma once

class BinaryTree
{

	private:
		struct Node {
			int key;
			Node *left;
			Node *right;
		};
		Node *root;

		Node *CreateLeaf(int key);

		void AddPrivate(int key, Node *ptr);
		bool SearchPrivate(int key, Node *ptr);
		void PrintPrivate(Node *ptr);

	public:
		BinaryTree();

		void Add(int key);
		void Print();
		bool Search(int key);
};

// CPP FILE
#include <iostream>

#include "BinaryTree.h"

using namespace std;


BinaryTree::BinaryTree()
{
	this->root = nullptr;

}


// Creates new leaf with nullpointers and returns it

BinaryTree::Node *BinaryTree::CreateLeaf(int key) {
	Node *NewNode = new Node;
	NewNode->key = key;
	NewNode->left = nullptr;
	NewNode->right = nullptr;

	return NewNode;
}

// public method to add a number to the tree
// calls private method which does the work

void BinaryTree::Add(int key)
{
	AddPrivate(key, this->root);
}


//private method to Add a number to the tree

void BinaryTree::AddPrivate(int key, Node *ptr)
{
	if (this->root == nullptr)
	{
		this->root = CreateLeaf(key);
	}
	else if (key < ptr->key)
	{
		if (ptr->left != nullptr)
		{
			AddPrivate(key, ptr->left);
		}
		else
		{
			ptr->left = CreateLeaf(key);
		}
	}
	else if (key > ptr->key)
	{
		if (ptr->right != nullptr)
		{
			AddPrivate(key, ptr->right);
		}
		else
		{
			ptr->right = CreateLeaf(key);
		}
	}
	else
	{
		cout << key << " has already been added " << endl;
	}
}

bool BinaryTree::Search(int key)
{
	return SearchPrivate(key, this->root);
}

bool BinaryTree::SearchPrivate(int key, Node *ptr)
{
	if (ptr->key == key)
	{
		return true;
	}
	else if (key < ptr->key)
	{
		if (ptr->left == nullptr)
		{
			return false;
		}
		else
		{
			SearchPrivate(key, ptr->left);
		}
	}
	else if (key > ptr->key)
	{
		if (ptr->right == nullptr)
		{
			return false;
		}
		else
		{
			SearchPrivate(key, ptr->right);
		}
	}
}

void BinaryTree::Print() {
	PrintPrivate(this->root);
}

void BinaryTree::PrintPrivate(Node *ptr) {
	if (this->root == nullptr) {
		return;
	}
	else {

		std::cout << ptr->key << std::endl;

		if (ptr->right) {
			PrintPrivate(ptr->right);
		}
		if (ptr->left) {
			PrintPrivate(ptr->left);
		}
	}
}