#include <cassert>
#include <iostream>
#include <istream>
#include <memory>
#include <string>
#include <string_view>
#include <tuple>

/*
Don't be scared, the code contains a lot of extra comments and hints so it looks longer than it is.

(You are free to modify the code as you see fit if you want to change the design, naming, etc.)

Simply look at the TODOs and try to implement them one by one (and fix the FIXMEs).
*/

class Node {
    // TODO: might be useful to uncomment the following line (this allows `Tree` to access private members of `Node`)
    friend class Tree;
public:
    // `value_{value}` initialization is allowed in the *constructor initializer list* even though value_ is const
    //  (constructor initializer list begins with a colon after the constructor declarator and ends before the constructor body)
    Node(const std::string& value) : value_{value} {
    }

    // this is a special reference called *rvalue reference*, the `value` can be std::move'd instead of copying
    // we can use this overload by calling `Node{std::move(value)}` or by passing a temporary: `Node(std::string{"value"})`
    Node(std::string&& value) : value_{std::move(value)} {
    }

    // returns a read-only reference to the value
    // the const after the function arguments means that the method doesn't modify the object
    const std::string& value() const { return value_; }

    // returns an observer pointer to the left/right child
    Node* left() const { return left_.get(); }
    Node* right() const { return right_.get(); }

    // call this method as `node.set_left(std::move(new_left))` or with a temporary: `node.set_left(std::make_unique<Node>(...))`,
    //   the source object is automatically set to nullptr
    void set_left(std::unique_ptr<Node>&& new_left) {
        set_child(left_, this, std::move(new_left));

        // left_ = std::move(new_left);
        // if (left_) {
        //     left_->parent_ = this;
        // }
    }

    void set_right(std::unique_ptr<Node>&& new_right) {
        set_child(right_, this, std::move(new_right));
    }

    static void set_child(std::unique_ptr<Node>& child, Node* parent, std::unique_ptr<Node>&& new_child) {
        child = std::move(new_child);

        if (child) {
            child->parent_ = parent;
        }
    }

private:
    // Modifying the node's value is not allowed:
    const std::string value_;
    std::unique_ptr<Node> left_, right_;
    Node* parent_; // observer pointer to the parent node
};

class Tree {
public:
    // (implicitly defined) Tree() : root_{nullptr} {}
    // we can request the constructor explicitly by writing `Tree() = default;`

    // this is a special reference called *rvalue reference*, the `value` can be std::move'd instead of copying
    void insert(std::string&& value) {
        // TODO: insert the value into the tree using std::move to avoid copying
        // if the value is already in the tree, do nothing
    }

    // notice that the value is passed by value, as std::string_view already represents a reference
    void remove(std::string_view value) {
        // remove the value from the tree

        // 1. if the value is not in the tree, do nothing
        auto [node_ptr, parent] = find_with_parent(value);

        // auto tuple = find_with_parent(value);
        // std::get<0>(tuple);

        // (a, b)  = c

        if (!node_ptr) {
            return;
        }
        // 2. if the removed node has up to one child, replace it with the child
        // 3.

        if (node_ptr->left_ == nullptr || node_ptr->right_ == nullptr) {
            std::unique_ptr<Node>& child = (node_ptr->left_ != nullptr)
                ? node_ptr->left_
                : node_ptr->right_;

            Node::set_child(node_ptr, parent, std::move(child));
            return;
        }

        // 4. if the removed node has two children, replace it with the smallest node from the right subtree (see Tree::min)
        // (4.a) trivial special case: if the right child has no left child, it is the smallest node

        std::unique_ptr<Node>* min_node_ptr = min(&node_ptr->right_);

        assert(min_node_ptr != nullptr && *min_node_ptr != nullptr);

        (*min_node_ptr)->set_left(std::move(node_ptr->left_));

        if (*min_node_ptr == node_ptr->right_) {
            Node::set_child(node_ptr, parent, std::move(node_ptr->right_));

            return;
        }

        // (4.b) general case: the smallest node is the leftmost node in the right subtree
        std::unique_ptr<Node> right_subtree = std::move(node_ptr->right_);
        auto min_parent = (*min_node_ptr)->parent_;
        Node::set_child(node_ptr, parent, std::move(*min_node_ptr));
        min_parent->set_left(std::move(node_ptr->right_));
        node_ptr->set_right(std::move(right_subtree));
    }

    Node* find(std::string_view value) const {
        // find the node with the given value and return it
        // if the value is not in the tree, return nullptr

        return /* TODO: change this */ nullptr;
    }

    void clear() {
        // remove all nodes from the tree
        // hint: children of a node are automatically deleted when the node is deleted

        // root_ = nullptr;
        root_.reset();
    }

    void print() const {
        // print the tree in-order: for each node, print the left subtree, then the node itself, then the right subtree
        // print each string on a separate line and indent it by the depth of the node (the root has depth 0)
        //   (use std::string(depth, '\t') to create the indentation string)
        // end the output with an extra newline

    }

private:
    // static method as it doesn't require to access the Tree (might as well be a Node method)
    static std::unique_ptr<Node>* min(std::unique_ptr<Node>* node) {
        // TODO: this helper function might be useful for the remove method, it just walks to the leftmost node
        assert(node != nullptr && *node != nullptr);

        while ((*node)->left_) {
            node = &(*node)->left_;
        }

        return node;
    }

    std::tuple<std::unique_ptr<Node>&, Node*> find_with_parent(std::string_view value) {
        // ref to unique_ptr to the found node and the parent node (or the last visited node if not found)

        std::unique_ptr<Node>* current = &root_;
        Node* parent = nullptr;

        assert (current != nullptr);

        // ptr->member is shorthand for (*ptr).member

        while (*current != nullptr) {
            auto cmp = value <=> (*current)->value(); // (**current).value();

            // cmp < 0 -> value < (*current)->value()
            // cmp == 0 -> value == (*current)->value()
            // cmp > 0 -> value > (*current)->value()

            if (cmp == 0) {
                return {*current, parent};
            } else if (cmp < 0) {
                parent = current->get();
                current = &(*current)->left_;
            } else { // cmp > 0
                parent = current->get();
                current = &(*current)->right_;
            }

            assert(current != nullptr);
        }

        assert (current != nullptr);

        return {*current, parent};
    }

    std::unique_ptr<Node> root_;
};

void program_loop(Tree &tree, std::istream& in = std::cin) {
    // TODO implement the program loop using Tree methods
}

int main(int argc, char* argv[]) {
    // create the tree object on the stack
    Tree tree;
    program_loop(tree); // TODO: if argc > 1, open the file and pass it to program_loop
}