#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) /* FIXME (uncomment this): : value_{value} */ {
        value_ = value; // FIXME: this is not allowed, simply remove this line and uncomment the initializer list (above)
    }

    // 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); // FIXME: this is not allowed
    }

    // 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) {
        // TODO move the ownership of the new left child to this node
    }

    void set_right(std::unique_ptr<Node>&& new_right) {
        // TODO move the ownership of the new right child to this node
    }

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

        // 2. if the removed node has no children, simply remove it

        // 3. if the removed node has one child, replace it with the child

        // 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

    }

    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
    }

    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)
    }

private:
    // static method as it doesn't require to access the Tree (might as well be a Node method)
    static Node* min(Node* node) {
        // TODO: this helper function might be useful for the remove method, it just walks to the leftmost node

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

    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
}