#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;
}