// CS301P Lab 4 Problem KST Learning

#include<iostream>
#include<conio.h>
using namespace std;

class Node
{
	private:
		int data;
		Node *left;
		Node *right;
		
	public:
		void setData(int d)
		{
			data = d;
		}
		void setLeft(Node *ptr)
		{
			left = ptr;
		}
		void setRight(Node *ptr)
		{
			right = ptr;
		}
		int getData()
		{
			return data;
		}
		Node* getLeft()
		{
			return left;
		}
		Node* getRight()
		{
			return right;
		}
};

class BST
{	
	private:
		Node *Root;
		
	public:
		BST()
		{
			Root = NULL;
		}
		
		void insert(int d)
		{
			Node *newNode = new Node;
			newNode -> setData(d);
			newNode -> setLeft(NULL);
			newNode -> setRight(NULL);
			
			if(Root == NULL)
			{
				Root = newNode;
			}
			else
			{
				Node *pre = Root;
				Node *ptr = Root;
				while(ptr != NULL)
				{
					if(d < ptr -> getData())
					{
						pre = ptr;
						ptr = ptr -> getLeft();
						if(ptr == NULL)
						{
							pre -> setLeft(newNode);
						}
					}
					else if(d > ptr -> getData())
					{
						pre = ptr;
						ptr = ptr -> getRight();
						if(ptr == NULL)
						{
							pre -> setRight(newNode);
						}
					}
					else
					{
						cout << "\n\n*** Duplicate Value Found ***";
						delete newNode;
						break;
					}
				}
			}
		}
		
		int BSTMin()
		{
			Node *ptr = Root;
			while(ptr -> getLeft() != NULL)
			{
				ptr = ptr -> getLeft();
			}
			return ptr -> getData();
		}
		
		int BSTMax()
		{
			Node *ptr = Root;
			while(ptr -> getRight() != NULL)
			{
				ptr = ptr -> getRight();
			}
			return ptr -> getData();
		}
};

main()
{
	BST obj;
	string names[] = {"Saleh","Ali","Umar","Musaddiq","Rehman","Hassaan"};
	int totalNames = sizeof(names)/sizeof(names[0]);
	cout << "Inserting the Length of Names in BST Nodes One By One";
	cout << "\n\n-----------------------------------------------------\n\n";
	for(int i=0; i<totalNames; i++)
	{
		cout << "Length of "<< names[i] << " is: " << names[i].length() << "\n\n";
		obj.insert(names[i].length());
	}
	cout << "\nValue of BST Minimum Node is: " << obj.BSTMin();
	cout << "\nValue of BST Maximum Node is: " << obj.BSTMax();
	getch();
	return 0;
}