#include <iostream>
using namespace std;

// Define the structure of a tree node
struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;

    // Constructor to create a new node
    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

// Binary Tree class
class BinaryTree {
private:
    TreeNode* root;

    // Helper function for in-order traversal
    void inorderHelper(TreeNode* node) {
        if (node == nullptr) return;
        inorderHelper(node->left);
        cout << node->value << " ";
        inorderHelper(node->right);
    }

    // Helper function for pre-order traversal
    void preorderHelper(TreeNode* node) {
        if (node == nullptr) return;
        cout << node->value << " ";
        preorderHelper(node->left);
        preorderHelper(node->right);
    }

    // Helper function for post-order traversal
    void postorderHelper(TreeNode* node) {
        if (node == nullptr) return;
        postorderHelper(node->left);
        postorderHelper(node->right);
        cout << node->value << " ";
    }

    // Helper function to insert a node recursively
    TreeNode* insertHelper(TreeNode* node, int value) {
        // If the tree is empty, return a new node
        if (node == nullptr) return new TreeNode(value);

        // Otherwise, recur down the tree
        if (value < node->value)
            node->left = insertHelper(node->left, value);
        else
            node->right = insertHelper(node->right, value);

        return node;
    }

public:
    // Constructor
    BinaryTree() : root(nullptr) {}

    // Public insert function
    void insert(int value) {
        root = insertHelper(root, value);
    }

    // Public function to perform in-order traversal
    void inorder() {
        inorderHelper(root);
        cout << endl;
    }

    // Public function to perform pre-order traversal
    void preorder() {
        preorderHelper(root);
        cout << endl;
    }

    // Public function to perform post-order traversal
    void postorder() {
        postorderHelper(root);
        cout << endl;
    }
};

// Driver code
int main() {
    BinaryTree tree;

    // Inserting nodes into the binary tree
    tree.insert(50);
    tree.insert(30);
    tree.insert(20);
    tree.insert(40);
    tree.insert(70);
    tree.insert(60);
    tree.insert(80);

    
        cout << "In-order traversal: ";
            tree.inorder();  // Should print: 20 30 40 50 60 70 80

        cout << "Pre-order traversal: ";
                tree.preorder(); // Should print: 50 30 20 40 70 60 80

        cout << "Post-order traversal: ";
                tree.postorder(); // Should print: 20 40 30 60 80 70 50

    return 0;
    
}