#include<bits/stdc++.h>
using namespace std;

struct BinaryTree{
    int data;
    BinaryTree *left;
    BinaryTree *right;

    BinaryTree(int _data) : data(_data), left(nullptr), right(nullptr) {}
};

BinaryTree* createTree(BinaryTree* root, int data) {
    if(root == nullptr){
        return new BinaryTree(data);
    }
    if(root->data < data){
        root->left = createTree(root->left, data);
    }
    else {
        root->right = createTree(root->right, data);
    }
    return root;
}

void inorder(BinaryTree *root) {

    if(root == nullptr) {
        return;
    }
    inorder(root->left);
    cout << root->data << ' ';
    inorder(root->right);
}

void postorder(BinaryTree *root) {
    if(root == nullptr) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->data << ' ';
}

int main() {
    BinaryTree* root = nullptr;
    bool flag = true;
    while(1) {
        cout << "1. Insert noden";
        cout << "2. Postorder traversaln";
        cout << "3. Inorder traversaln";
        cout << "4. Exitn";
        int choice;
        cin >> choice;

        switch(choice) {
        case 1:
            cout << "Enter the element you want to insert: ";
            int  data;
            cin >> data;
            if(flag) {
                root = createTree(root, data);
                flag = false;
            }
            else createTree(root, data);
            break;
        case 2:
            inorder(root);
            cout << endl;
            break;
        case 3:
            postorder(root);
            cout << endl;
            break;
        case 4:
            return 0;
        default:
            cout << "Invalid Option Chosenn";
            break;
        }
    }

    return 0;
}