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

#include "stdafx.h"
#include<iostream.h>
#include<assert.h>
class btNode
{
public:
	int info;
	btNode * left;
	btNode * right;
};

class Tree 
{
private:
	btNode * root;
public:
	Tree(); 
	Tree(int);
	btNode* GetRoot();
	int  pr(btNode*);
	int Insert(btNode*,int);
};


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->info;
		pr(node->right);
	}
	return 0;

}


int Tree::Insert(btNode* node,int n)
{

		if (!node) 
		{
			root=new btNode;
			root->left=new btNode;
			root->right=NULL;
			root->left->left=root->left->right=NULL;
			root->left->info=n;
			return 1;
		}

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


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