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

class BST {
private:
    struct Node {
        int key;
        Node* left;
        Node* right;

        Node(int value) {
            key = value;
            left = right = nullptr;
        }
    };

    Node* root;
    int sz = 0;

    Node* insert(Node* root, int value) {
        if (root == nullptr) return new Node(value);
        if (value < root->key) 
            root->left = insert(root->left, value);
        else 
            root->right = insert(root->right, value);
        return root;    
    }

    bool search(Node* root, int value) {
        if (root == nullptr) return false;
        if (value < root->key) 
            return search(root->left, value);
        if (value > root->key)
            return search(root->right, value);
        return true;
    }

    Node* getMin(Node* root) {
        while (root->left != nullptr) {
            root = root->left;
        }
        return root;
    }

    Node* getMax(Node* root) {
        while (root->right != nullptr) {
            root = root->right;
        }
        return root;
    }

    void inOrder(Node* root) {
        if (root == nullptr) return;
        inOrder(root->left);
        cout << root->key << ' ';
        inOrder(root->right);
    }

    void preOrder(Node* root) {
        if (root == nullptr) return;
        cout << root->key << ' ';
        preOrder(root->left);
        preOrder(root->right);
    }

    void postOrder(Node* root) {
        if (root == nullptr) return;
        postOrder(root->left);
        postOrder(root->right);
        cout << root->key << ' ';
    }

public: 
    BST() {
        root = nullptr;
    }

    int size() {
        return sz;
    }

    bool empty() {
        return root == nullptr;
    }

    void insert(int value) {
        root = insert(root, value);
        sz++;
    }

    bool search(int value) {
        return search(root, value);
    }

    int getMin() {
        if (empty()) throw runtime_error("The BST is Empty");
        return getMin(root)->key;
    }

    int getMax() {
        if (empty()) throw runtime_error("The BST is Empty");
        return getMax(root)->key;
    }

    bool remove(int value) {
        //  TO DO
        return true;
    }

    void inOrder() {
        inOrder(root);
        cout << '\n';
    }

    void preOrder() {
        preOrder(root);
        cout << '\n';
    }

    void postOrder() {
        postOrder(root);
        cout << '\n';
    }
};

int main()
{
    BST tree;

    // cout << tree.getMin() << '\n';

    tree.insert(5);
    tree.insert(1);
    tree.insert(3);
    tree.insert(7);
    tree.insert(8);

    cout << tree.getMin() << '\n';
    cout << tree.getMax() << '\n';

    // tree.search(3);
    // tree.search(6);

    // tree.inOrder();
    // tree.preOrder();
    // tree.postOrder();

    return 0;
}