# include <iostream>
# include <cstdlib>
using namespace std;
/*
 * Node Declaration
 */
/** lexer.h*/
 class ParseTree {
	int			linenumber;
	ParseTree	*left;
	ParseTree	*right;

public:
	ParseTree(int n, ParseTree *l = 0, ParseTree *r = 0) : linenumber(n), left(l), right(r) {}
extern void error(int linenum, const string& message);

enum TypeForNode { INT_TYPE, STRING_TYPE, ERROR_TYPE }
}

struct node
{
    int info;
    struct node *left;
    struct node *right;
}*root;
 
/*
 * Class Declaration
 */
class BST
{
    public:
        void insert(node *, node *);
        void postorder(node *);
        void display(node *, int);
        BST()
        {
            root = NULL;
        }
};
/*
 * Main Contains Menu
 */
int main()
{
    int choice, num;
    BST bst;
    node *temp;
    while (1)
    {
        cout<<"-----------------"<<endl;
        cout<<"Operations on ParseTree"<<endl;
        cout<<"-----------------"<<endl;
        cout<<"L"<<endl;
        cout<<"u"<<endl;
        cout<<"R"<<endl;
        cout<<"U"<<endl;
        cout<<"N";
        cin>>choice;
        switch(choice)
        {
        case 1:
            temp = new node;
            cout<<"print letter L : ";
            cin>>temp->info;
            bst.insert(root, temp);
            break;
        case 2:
            cout<<"print letter u:"<<endl;
            bst.postorder(root);
            cout<<endl;
            break;
        case 3:
            cout<<"print letter R:"<<endl;
            bst.display(root,1);
            cout<<endl;
            break;
        case 4:
            cout<<"print letter U:"<<endl;
            bst.display(root,1);
            cout<<endl;
            break;  
        case 5:
            cout<<"print letter N:"<<endl;
            bst.display(root,1);
            cout<<endl;
            break;
        case 6:
            exit(1);
        default:
            cout<<""<<endl;
        }
    }
}
 
 
/*
 * Inserting Element into the Tree
 */
void BST::insert(node *tree, node *newnode)
{
    if (root == NULL)
    {
        root = new node;
        root->info = newnode->info;
        root->left = NULL;
        root->right = NULL;
        cout<<"Root Node is Added"<<endl;
        return;
    }
    if (tree->info == newnode->info)
    {
        cout<<"Element already in the tree"<<endl;
        return;
    }
    if (tree->info > newnode->info)
    {
        if (tree->left != NULL)
        {
            insert(tree->left, newnode);
        }
        else
        {
            tree->left = newnode;
            (tree->left)->left = NULL;
            (tree->left)->right = NULL;
            cout<<"Node Added To Left"<<endl;
            return;
        }
    }
    else
    {
        if (tree->right != NULL)
        {
            insert(tree->right, newnode);
        }
        else
        {
            tree->right = newnode;
            (tree->right)->left = NULL;
            (tree->right)->right = NULL;
            cout<<"Node Added To Right"<<endl;
            return;
        }
    }
}
 
/*
 * Postorder Traversal
 */
void BST::postorder(node *ptr)
{
    if (root == NULL)
    {
        cout<<"Tree is empty"<<endl;
        return;
    }
    if (ptr != NULL)
    {
        postorder(ptr->left);
        postorder(ptr->right);
        cout<<ptr->info<<"  ";
    }
}
 
/*
 * Display Tree Structure
 */
void BST::display(node *ptr, int level)
{
    int i;
    if (ptr != NULL)
    {
        display(ptr->right, level+1);
        cout<<endl;
        if (ptr == root)
            cout<<"Root->:  ";
        else
        {
            for (i = 0;i < level;i++)
                cout<<"       ";
	}
        cout<<ptr->info;
        display(ptr->left, level+1);
    }
     if (cin.fail()){
        cin.clear();
        cin.ignore(100,'\n'); // it will ignore 100 characters or get to the end of the line.
    }
}