class Node {
public:
    int value;
    Node* left;
    Node* right;

    Node(int value) {
        this->value = value;
        left = nullptr;
        right = nullptr;
    }
};

class BinaryTree {
private:
    Node* root;
    const int MAX_KEY = 999;
public:

    BinaryTree() {
        root = nullptr;
    }

    void add(int value) {
        if (value < MAX_KEY) {
            Node *node = new Node(value);
            if (root != nullptr) {
                Node *current = root;
                Node *prev;
                bool posNotFound = true;
                while (posNotFound) {
                    prev = current;
                    if (value < current->value) {
                        current = current->left;
                        if (current == nullptr) {
                            prev->left = node;
                            posNotFound = false;
                        }
                    } else {
                        current = current->right;
                        if (current == nullptr) {
                            prev->right = node;
                            posNotFound = false;
                        }
                    }
                }
            } else {
                root = node;
            }
        }
    }

    void deleteValue(int value) {
        root = deleteRecursively(root, value);
    }

    Node* deleteRecursively(Node *current, int value) {
        if (current == nullptr) {
            return nullptr;
        }
        if (value < current->value) {
            current->left = deleteRecursively(current->left, value);
            return current;
        } else if (value > current->value) {
            current->right = deleteRecursively(current->right, value);
            return current;
        }
        if (current->left == nullptr) {
            return current->right;
        } else if (current->right == nullptr) {
            return current->left;
        } else {
            current->value = findSmallestKey(current->right);
            current->right = deleteRecursively(current->right, current->value);
            return current;
        }
    }

    int findSmallestKey(Node *current) {
        return current->left == nullptr ? current->value : findSmallestKey(current->left);
    }

    std::string toString() {
        std::string result = "";
        return recursiveDepthFirst(root, result);
    }

    void printLeafs() {
        int counter = 0;
        recursivePrintLeafs(root, counter);
        std::cout << "amount:\n";
        std::cout << counter;
    }

    void recursivePrintLeafs(Node *current, int &counter) {
        if (current != nullptr) {
            recursivePrintLeafs(current->left, counter);
            if (current->left == nullptr && current->right == nullptr) {
                std::cout << current->value << std::endl;
                counter++;
            }
            recursivePrintLeafs(current->right, counter);
        }
    }

    std::string recursiveDepthFirst(Node *current, std::string &result) {
        if (current != nullptr) {
            recursiveDepthFirst(current->left, result);
            result +=  std::to_string(current->value) + " ";
            recursiveDepthFirst(current->right, result);
        }
        return result;
    }



    std::string toStringBreadthFirst() {
        std::string result = "";
        if (root != nullptr) {
            std::queue<Node*> nodes;
            nodes.push(root);
            while (!nodes.empty()) {
                Node *current = nodes.front();
                nodes.pop();
                result +=  std::to_string(current->value) + " ";
                if (current->left != nullptr) {
                    nodes.push(current->left);
                }

                if (current->right != nullptr) {
                    nodes.push(current->right);
                }
            }
        } else {
            result = "";
        }
        return result;
    }


    void clear() {
        while (root != nullptr) {
            deleteValue(root->value);
        }
    }

};