#include <iostream>
#include <cstring>

using std::cout;
using std::endl;

struct Node
{
    int value{0};
    Node* left{nullptr};
    Node* right{ nullptr };
};


class Lista
{

    Node* root{ nullptr };
    int count{ 0 };

    public:

    void add(int v)
    {
        Node* node = new Node();
        node->value = v;
        count++;
        if (!root)
        {
            root = node;
            return;
        }
        _add(root,node);
    }


    void print()
    {
        if(root)
        {
            _print(root);
        }
    }

    bool find(int value)
    {
        if (!root) return false;
        return _find(root,value);
    }

    ~Lista()
    {
        _destroy(root);
    }


    private:

    void _destroy(Node* node) {
        if (!node) return;
        _destroy(node->left);
        _destroy(node->right);
        delete node;
    }
    bool _find(Node* root,int value)
    {
        if (!root) return false;
        if (root->value == value) return true;
        if (root->value > value) return _find(root->left, value);
        if (root->value < value) return _find(root->right, value);
        return false;
    }

void _print(Node *root)
{
    if (root)
    {
        if (root->left) _print(root->left);
        cout << root->value << endl;
        if (root->right) _print(root->right);
    }
}


    void _add(Node* _root, Node* node)
    {
        if (_root->value > node->value)
        {
            if (!_root->left)
            {
                _root->left = node;
                return;
            }
            _add(_root->left, node);
        }
        else
        {
            if (!_root->right)
            {
                _root->right = node;
                return;
            }
            _add(_root->right, node);
        }
        }
};


int main()
{

    Lista lista;


    lista.add(0);
    lista.add(1);
    lista.add(2);
    lista.add(3);

    lista.add(-3);
    lista.add(-2);
    lista.add(-1);


    if(lista.find(5))
    {
        cout << "FOUND" << endl;
    } else
    {
        cout << "NOT FOUND" << endl;
    }


    lista.print();

    // lista.print();

    // lista.clear();
    return 0;
}