#include <bits/stdc++.h>
using namespace std;
template <class T>
class BST;

template <class T>
class BSTNode {
    T key;
    BSTNode* left;
    BSTNode* right;

public:
    BSTNode() : left(nullptr), right(nullptr){}
    BSTNode(const T& el, BSTNode* l = nullptr, BSTNode* r = nullptr) {
        key = el;
        left = l;
        right = r;
    }
    BSTNode* getLeft() const {return left;}
    BSTNode* getRight() const {return right;}
    T& getKey() { return key; }
    friend class BST<T>;
};

template <class T>
class BST {
protected:
    BSTNode<T>* root;
public:
    BST() {root = nullptr;}
    void clear() {root = nullptr;}
    bool isEmpty() {return root == nullptr;}

    T* search(const T& el) {
        BSTNode<T>* p = root;
        while (p != nullptr) {
            if (p->getKey() == el) {
                return &(p->key);
            }
            if (p->getKey() < el) {
                p = p->getRight();
            }else p = p->getLeft();
        }
        return nullptr;
    }

    void insert(const T& el) {
        BSTNode<T> *p = root, *prev = nullptr;

        //finding a place to insert the new node
        while (p != nullptr) {
            prev = p;
            if (p->key < el) p = p->right;
            else p = p->left;
        }

        //inserting the new node
        if (root == nullptr) root = new BSTNode<T>(el);
        else if (prev->key < el) {
            prev->right = new BSTNode<T>(el);
        }else prev->left = new BSTNode<T>(el);
    }
};



int main() {
    BST<int> binary;
    binary.insert(15);
    binary.insert(20);
    int* found = binary.search(15);
    cout << *found;

    return 0;
}