template<typename Type>
class NodeIterator {
 private:
    const Node <Type> *p;
    const Node<Type> *root;

 public:
    NodeIterator(): p(nullptr), root(nullptr) {}

    NodeIterator(shared_ptr<const Node <Type>> p,
                 shared_ptr<const Node <Type>> root): p(p.get()), root(root.get()) {}

    NodeIterator(shared_ptr<const Node<Type>> root): root(root.get()) {
        p = this->root;
        while (p != nullptr && p->l_son != nullptr) {
            p = p->l_son.get();
        }
    }

    NodeIterator(const NodeIterator &other): p(other.p), root(other.root) {}

    NodeIterator &operator=(const NodeIterator &other) {
        p = other.p;
        root = other.root;
        return *this;
    }

    ~NodeIterator() {
    }

    const Type &operator*() const {
        return p->key;
    }

    const Type *operator->() const {
        return &(p->key);
    }

    bool operator==(const NodeIterator<Type> &other) const {
        return (p == other.p && root == other.root);
    }

    bool operator!=(const NodeIterator<Type> &other) const {
        return !(p == other.p && root == other.root);
    }

    NodeIterator &operator++() {
        if (p == nullptr) {
            return *this;
        }

        if (p->r_son != nullptr) {
            p = p->r_son.get();
        } else {
            while (p->parent != nullptr && p->parent->r_son.get() == p) {
                p = p->parent.get();
            }
            p = p->parent.get();

            return *this;
        }

        while (p->l_son != nullptr) {
            p = p->l_son.get();
        }

        return *this;
    }

    NodeIterator operator++(int) {
        auto res = *this;
        ++*this;

        return res;
    }

    NodeIterator &operator--() {
        if (p == nullptr) {
            p = root;
            if (p == nullptr) {
                return *this;
            }

            while (p->r_son != nullptr) {
                p = p->r_son.get();
            }

            return *this;
        }

        if (p->l_son != nullptr) {
            p = p->l_son.get();
            while (p->r_son != nullptr) {
                p = p->r_son.get();
            }

            return *this;
        }

        while (p->parent != nullptr && p->parent->l_son.get() == p) {
            p = p->parent.get();
        }
        p = p->parent.get();

        return *this;
    }

    NodeIterator operator--(int) {
        auto res = *this;
        --*this;

        return res;
    }
};