#include<iostream.h>

typedef int DataType;
struct node{
	DataType data;
	node* LChild;
	node* RChild;
};

void Preorder(node* tree)
{
	if(tree!=NULL)
	{
		cout<<tree->data<<" ";
		Preorder(tree->LChild);
		Preorder(tree->RChild);
	}
}

void Inorder(node* tree)
{
	if(tree!=NULL)
	{
		Inorder(tree->LChild);
		cout<<tree->data<<" ";
		Inorder(tree->RChild);
	}
}

void Postorder(node* tree)
{
	if (tree!=NULL)
	{
		Postorder(tree->LChild);
		Postorder(tree->RChild);
		cout<<tree->data<<" ";
	}
}

int insert (node* &tree, const int& num)
{
	if (tree == NULL)		//tree is empty
	{
		tree = new node;
		tree->LChild = NULL;
		tree->RChild= NULL;
		tree->data= num;
		return 0;
	}
	else if (num == tree->data)
		return insert(tree->LChild,num);	// tree is not empty
	else if (num <= tree->data)
		return insert(tree->LChild,num);
	else 
		return insert(tree->RChild,num);
}

int main(){
	node* tree=NULL;
	int num;
	int value;

	//inserting nodes
	cout<<"Please enter the number of node you want to key in...";
	cin>>num;
	for(int i=0; i<num; i++){
		cin>>value;
		insert(tree, value);
	}

	//In Order display
	cout<<"In Order:    ";
	Inorder(tree);
	cout<<endl<<endl;

	//Post Order
	cout<<"Post Order:    ";
	Postorder(tree);
	cout<<endl<<endl;

	//Pre Order display
	cout<<"Pre Order:    ";
	Preorder(tree);
	cout<<endl<<endl;

	return 0;
}