#include<iostream.h>
#include<conio.h>

struct node
{
node *LeftChild;
node *RightChild;
int data;
};

class tree
{
private:

node *root, *parent, *p_parent;

void preorder(node *currentnode)
{
if(currentnode)
{
cout<<currentnode->data<<endl;
preorder(currentnode->LeftChild);
preorder(currentnode->RightChild);
}
}

void inorder(node *currentnode)
{
if(currentnode)
{
inorder(currentnode->LeftChild);
cout<<currentnode->data<<endl;
inorder(currentnode->RightChild);
}
}


void postorder(node *currentnode)
{
if(currentnode)
{
postorder(currentnode->LeftChild);
postorder(currentnode->RightChild);
cout<<currentnode->data<<endl;
}
}

public:

tree()
{
root = NULL;
parent = NULL;
}

void insert(int x)
{
parent = root;
p_parent = NULL;

while(parent)
{
p_parent = parent;

if(x < parent->data)
parent = parent -> LeftChild;
else
parent = parent -> RightChild;
}

parent = new node;
parent -> LeftChild = NULL;
parent -> RightChild = NULL;
parent -> data = x;

if(!root)
root = parent;

else if(x < p_parent -> data)
p_parent -> LeftChild = parent;

else
p_parent -> RightChild = parent;
}

void PreOrder(void)
{
preorder(root);
}

void InOrder(void)
{
inorder(root);
}

void PostOrder(void)
{
postorder(root);
}

};

void main(void)
{
clrscr();

tree t;

t.insert(100);    // first simply inserting nodes in binary search tree
t.insert(90);
t.insert(80);
t.insert(92);
t.insert(70);
t.insert(140);
t.insert(200);
t.insert(160);
t.insert(85);
t.insert(95);
t.insert(150);
t.insert(180);
t.insert(98);

cout<<" PRE ORDER TRAVERSING OF BINARY SEARCH TREE "<<endl<<endl;

t.PreOrder();  // preorder traversing

getch();

clrscr();
cout<<" IN ORDER TRAVERSING OF BINARY SEARCH TREE "<<endl<<endl;

t.InOrder();   // inorder traversing

getch();

clrscr();
cout<<" POST ORDER TRAVERSING OF BINARY SEARCH TREE "<<endl<<endl;

t.PostOrder();  // post order traversing

getch();
}