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

struct node {
	int data;
	struct node* left;
	struct node* right;
};

struct node* NewNode(int);
void printTree(struct node*,int);
struct node* insert(struct node*, int);

void  main(void)
{
 struct node * root = '\0';
 int     choice;

 root = insert(root, 10);
 root = insert(root, 5);
 root = insert(root, -3);
 root = insert(root, 6);
 root = insert(root, 7);
 root = insert(root, 8);
 root = insert(root, 1);
 root = insert(root, 0);
 root = insert(root, -1);
 cout<<"\n please enter your choice:";
 cout<<"\n\t1) Inorder list";
 cout<<"\n\t2) Preorder list";
 cout<<"\n\t3) Postorder list";
 cin >> choice;
 printTree(root, choice);
 cout<<"\n press any key to exit...";
 getch();

}

struct node* NewNode(int data)
{
	struct node* node = new(struct node); // "new" is like "malloc"
	node->data = data;
	node->left = NULL;
	node->right = NULL;
   return(node);
}

void printTree(struct node* node, int choice)
{
      switch(choice)
      {
        case 1: if (node == NULL)     //inorder
                   return;
                printTree(node->left,1);
                cout<<node->data;
                printTree(node->right,1);
                break;
       case 2: if (node == NULL)     //preorder
                   return;
                cout<<node->data;
                printTree(node->left,2);
                printTree(node->right,2);
                break;
       case 3: if (node == NULL)     //postorder
                   return;
                printTree(node->left,3);
                printTree(node->right,3);
                cout<<node->data;
                break;
       default: cout<<"Sorry!! error in your input";
      }
}

struct node* insert(struct node* node, int data) {
// 1. If the tree is empty, return a new, single node
  if (node == NULL) {
     return(NewNode(data));
   }
  else {
// 2. Otherwise, recur down the tree
    if (data <= node->data)
       node->left = insert(node->left, data);
    else
       node->right = insert(node->right, data);
   return(node); // return the (unchanged) node pointer
}
}