#include <iostream>
#include <queue>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int d) {
        this->data = d;
        this->left = NULL;
        this->right = NULL;
    }
};

Node* insertIntoBST(Node* root, int d) {
    // base case 
    if (root == NULL) {
        root = new Node(d); // Create a new node
        return root; // Return the newly created node
    }
    if (d > root->data) {
        // Insert in the right subtree
        root->right = insertIntoBST(root->right, d);
    } else {
        // Insert in the left subtree
        root->left = insertIntoBST(root->left, d);
    }
    return root; // Return the root of the subtree
}

void levelOrderTraversal(Node* root) {
    if (root == NULL) 
        return; // If the tree is empty, return

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
        cout << temp->data << " "; // Print the current node's data

        // Push left and right children into the queue
        if (temp->left) {
            q.push(temp->left);
        }
        if (temp->right) {
            q.push(temp->right);
        }
    }
    cout << endl; // Print a new line after level order traversal
}

void takeInput(Node*& root) {
    int data;
    cin >> data;

    while (data != -1) {
        root = insertIntoBST(root, data); // Update the root pointer
        
        // Print the current state of the BST after each insertion
        cout << "Current state of the BST after inserting " << data << ": ";
        levelOrderTraversal(root);
        
        cin >> data;
    }
}
void inorder(Node* root) {
    //base case
    if(root == NULL) {
        return ;
    }
    inorder(root->left);
    cout << root-> data << " ";
    inorder(root->right);
}
void preorder(Node* root) {
    //base case
    if(root == NULL) {
        return ;
    }
    cout << root-> data << " ";
    preorder(root->left);
    preorder(root->right);
}
void postorder(Node* root) {
    //base case
    if(root == NULL) {
        return ;
    }
    postorder(root->left);
    postorder(root->right);
    cout << root-> data << " ";
}
Node* minVal(Node* root){
    Node* temp = root;
    
    while(temp->left != NULL){
        temp = temp->left;
    }
    return temp;
}
Node* maxVal(Node* root){
    Node* temp = root;
    
    while(temp->right != NULL){
        temp = temp->right;
    }
    return temp;
}
int main() {
    Node* root = NULL;
    cout << "Enter the data for BST (end with -1): ";
    takeInput(root);
    
    cout << "printing inorder" << endl;
    inorder(root);
    
    cout << endl <<"printing preorder" << endl;
    preorder(root);
    
    cout << endl<<  "printing postorder" << endl;
    postorder(root);
    
    cout <<endl <<" min value is "<< minVal(root) -> data << endl;
    cout <<" min value is "<< maxVal(root) -> data << endl;
    
    
    
    
    return 0;
}


//// Time complexity = O(logn)