// Syed Rais Ahmad
//Assignment 8 Ans 4.
//Search & Insert in Binary Search Tree.

#include "stdafx.h"
#include<iostream.h>
#include<assert.h>

class btNode
{
public:
	int key;
	int rec;
	btNode * left;
	btNode * right;
	
};

class Tree 
{
private:
	btNode * root;
public:
	Tree(); 
	Tree(int);
	btNode* GetRoot();
	int  pr(btNode*);
	int Insert(btNode*,int,int);
	bool Search(btNode*,int);
	void SInsert(int key,int rec);
};


Tree::Tree()
{
	root=new btNode;
	root->left=NULL;
	root->right=NULL;
}


//Return the root's address
btNode * Tree::GetRoot()
{
	if (root->left) return root->left;
	else return NULL;
}

//print the values in tree
int Tree::pr(btNode * node)
{
	if (node)
	{
		pr(node->left);
		cout << '\n' << node->key;
		pr(node->right);
	}
	return 0;

}


int Tree::Insert(btNode* node,int key,int rec)
{

		if (!node) 
		{
			root=new btNode;
			root->left=new btNode;
			root->right=NULL;

			root->left->left=root->left->right=NULL;
			root->left->rec=rec;
			root->left->key=key;
			return 1;
		}

		if (node->key > key) 
		{
			if (!node->left) 
			{	node->left=new btNode;
				node=node->left;
				node->left=node->right=NULL;
				node->key=key;
				node->rec=rec;
				return 1;
			}
			Insert(node->left,key,rec);
		}
		else 
		{
			if (!node->right) 
			{
				node->right=new btNode;
				node=node->right;
				node->right=node->left=NULL;
				node->rec=rec;
				node->key=key;
				return 1;
			}
			Insert(node->right,key,rec);
		}
	return 0;
}


bool Tree::Search(btNode* node, int key)
{
	if (node)
	{
	if (node->key == key) return true;
	else
		Search(node->left,key);
		Search(node->right,key);
	}
		return false;
}
		

void Tree::SInsert(int key,int rec)
{
	if (!Search(root->left,key))
		Insert(root->left,key,rec);
}


int main(int argc, char* argv[])
{
	Tree t;
	t.SInsert(1,2);
	t.SInsert(2,3);
	
	t.pr(t.GetRoot());
	return 0;
}