#include <iostream>
#include <vector>
#include <ctime>

using std::string;
using std::cout;
using std::cin;
using std::vector;
using std::endl;
using std::swap;


class BST {
    struct Node {
        int value;
        Node* parent;
        Node* left;
        Node* right;
        Node(int value, Node* parent = nullptr, Node* left = nullptr, Node* right = nullptr);
    };
    Node* root;

public:
    BST();
    ~BST();

    Node* CereateNew(int value);
    Node* Insert(int value);
};

int main() {

}

BST::BST()
    : root(nullptr)
{}

BST::Node *BST::CereateNew(int value) {
    Node* new_node = new Node(value);
    return new_node;
}

BST::Node::Node(int value, BST::Node *parent, BST::Node *left, BST::Node *right)
        : value(value)
        , parent(parent)
        , left(left)
        , right(right)
{}

BST::Node *BST::Insert(int value) {
    if ( root == nullptr ) {
        root->value = value;
        return nullptr;
    }
   Node* currNode = root;
    bool done=false;

    while(true){
        while(true) {
            if(currNode->value < value) {
                if (currNode->left == nullptr) {
                    currNode->left = CereateNew(value);
                    currNode->left->parent = currNode;
                    done = true;
                    break;
                } else {
                    currNode = currNode->left;
                    break;
                }
            }
                if(currNode->value >= value) {
                    if (currNode->right == nullptr) {
                        currNode->right = CereateNew(value);
                        currNode->right->parent=currNode;
                        done = true;
                        break;
                    } else {
                        currNode = currNode->right;
                    }
                }
            }
        if(done) break;
        }
    }




}