#include <iostream>
#include <string>
using namespace std;


struct Participant
{
    int coefficient;
    string name;

};

template <class T>
struct Node
{
    T value;
    Node* left;
    Node* right;

    Node(T _value) {
        value = _value;
        left = NULL;
        right = NULL;
    }

    Node(T _value, Node<T>* _left, Node<T>* _right) {
        value = _value;
        left = _left;
        right = _right;
    }
    ~Node() {
        delete left;
        delete right;
    }
};

template <typename T>
class BinTree
{
public:
    Node<T>* root;

    BinTree() {
        root = NULL;
    }

    ~BinTree() {
        delete root;
    }

    bool insert(T x, string trace) {
        return insert_helper(x, trace, root);
    }

    unsigned height() {
        return height(root);
    }

    void get_leaves() {
        get_leaves(root);
    }

    int count_leaves() {
        return count_leaves_help(root, 0);
    }

    T max_leaf() {
        T maxLeaf = root->value;
        return max_leaf_help(root, maxLeaf);
    }

    bool find(T value) {
        return find_helper(value, root);
    }

    void findPath(T value) {
        find_path(value, root);
    }

    int count() {
        return count_help(root, 0);
    }

    int countEvens() {
        return count_evens(root, 0);
    }
    Node<T> * getRoot() const
    {
        return root;
    }
public:

    bool insert_helper(T x, string trace, Node<T>*& subRoot) {
        if (trace == "" && subRoot == NULL) {
            subRoot = new Node<T>(x, NULL, NULL);
            return true;
        }
        if (trace != "" && subRoot == NULL)
            return false;

        if (trace[0] == 'L') {
            trace.erase(trace.begin());
            insert_helper(x, trace, subRoot->left);
        }
        if (trace[0] == 'R') {
            trace.erase(trace.begin());
            insert_helper(x, trace, subRoot->right);
        }
    }

    T height(Node<T>* sub_root) {
        if (sub_root == NULL)
            return 0;
        unsigned left = height(sub_root->left);
        unsigned right = height(sub_root->right);

        return 1 + (left > right ? left : right);
    }

    void get_leaves(Node<T>* sub_root) {
        if (sub_root == NULL)
            return;

        if (sub_root->left == NULL &&
            sub_root->right == NULL) {

            cout << sub_root->value;
        }
        get_leaves(sub_root->left);
        get_leaves(sub_root->right);
        cout << " ";
    }

    int count_leaves_help(Node<T>* currentRoot, int counter) {
        if (currentRoot == NULL)
            return 0;
        if (currentRoot->left == NULL && currentRoot->right == NULL)
            counter++;
        int countL = count_leaves_help(currentRoot->left, counter + 1);
        int countR = count_leaves_help(currentRoot->right, counter + 1);

        return (currentRoot->left == NULL && currentRoot->right == NULL ? 1 : 0) + countL + countR;
    }

    bool isLeaf(Node<T>* currentRoot) {
        if (currentRoot == NULL)
            return false;
        if (currentRoot->left == NULL && currentRoot->right == NULL)
            return true;
    }

    // Изкарва най-голямото листо
    T max_leaf_help(Node<T>* currentRoot, T maxLeaf) {
        if (currentRoot == NULL) {
            return maxLeaf;
        }
        if (isLeaf(currentRoot) == true) {
            if (maxLeaf <= currentRoot->value)
                maxLeaf = currentRoot->value;
        }
        else {
            unsigned maxL = max_leaf_help(currentRoot->left, maxLeaf);
            unsigned maxR = max_leaf_help(currentRoot->right, maxLeaf);

            maxLeaf = (maxL > maxR ? maxL : maxR);
        }
        return maxLeaf;
    }

    int count_help(Node<T>* currentRoot, int counter) {
        if (currentRoot == NULL)
            return 0;

        int counterL = count_help(currentRoot->left, counter);
        int counterR = count_help(currentRoot->right, counter);

        return 1 + counterL + counterR;
    }


    int count_evens(Node<T>* currentRoot, int counter) {
        if (currentRoot == NULL)
            return 0;

        int counterL = count_evens(currentRoot->left, counter);
        int counterR = count_evens(currentRoot->right, counter);

        return (currentRoot->value % 2 == 0 ? 1 : 0) + counterL + counterR;
    }

    //Well this one is obvious
    bool find_helper(T value, Node<T>* currentRoot) {
        if (currentRoot == NULL)
            return false;
        if (currentRoot->value == value)
            return true;
        else
            return find_helper(value, currentRoot->left) ||
            find_helper(value, currentRoot->right);

        return false;
    }

    void find_path(T value, Node<T>* currentRoot) {
        if (find_helper(value, currentRoot) == false) {
            cout << value << " is not found" << endl;
            return;
        }
        if (currentRoot->value == value) {
            cout << "Found " << value << endl;
        }
        else {

            if (find_helper(value, currentRoot->left) == true) {
                cout << "L->";
                find_path(value, currentRoot->left);
            }
            else if (find_helper(value, currentRoot->right) == true) {
                cout << "R->";
                find_path(value, currentRoot->right);
            }
        }
    }


};
template<class T>
bool find_helper_string(string value, Node<T>* currentRoot) {
        if (currentRoot == NULL)
            return false;
        if (value.compare(currentRoot->value) == 0)
            return true;
        else
            return find_helper(value, currentRoot->left) ||
            find_helper(value, currentRoot->right);

        return false;
    }


template <class T>
void findpath(string& _name, Node<T>*& root)
{

    if(_name.empty())
    {
        cout << "Error! "; return;
    }

    if (root == NULL)
    {
        cout << "Error! "; return;
    }
    //if (root->left == NULL && root->right == NULL) {
    //    cout  << root->value.name << endl;
    if(root->left->value.name.compare(_name) == 0 || root->right->value.name.compare(_name) == 0)
    {
        cout << root->left->value.name << " VS " << root->right->value.name << endl;
    }
    if(find_helper_string(_name, root->left))
    {
        findpath(_name, root->left);
    }
    if(find_helper_string(_name, root->right))
    {
        findpath(_name, root->right);
    }
}


int main()
{
   // Participant p {"lili", 8};
	BinTree<int> tr;
    tr.insert(5, " ");
	tr.insert(6, "L");
	tr.insert(8, "R");
	tr.insert(6, "RL");
	tr.insert(8, "RR");
	tr.insert(6, "LL");
	tr.insert(6, "LR");
	tr.insert(50, "LLR");
	tr.insert(25, "RLR");
	tr.insert(2, "RLL");
	tr.insert(2, "LRR");
	tr.insert(7, "LRL");
	tr.insert(19, "LLL");
//    Node<Participant> *t = tr.getRoot();
//    findpath("RR", t1);
    return 0;
}