template <typename U> struct PreOrderIterator;
template <typename T> struct BinaryTree;

template <typename T> struct Node
{
  T value;
  Node<T> *left = nullptr;
  Node<T> *right = nullptr;
  Node<T> *parent = nullptr;
  BinaryTree<T>* tree = nullptr;

  explicit Node(const T& value)
    : value(value) {}

  Node(const T& value, Node<T>* const left, Node<T>* const right)
    : value(value), left(left), right(right)
  {
    this->left->tree =this->right->tree = tree;
    this->left->parent = this->right->parent = this;
  }

  void set_tree(BinaryTree<T>* t)
  {
    tree = t;
    if (left) left->set_tree(t);
    if (right) right->set_tree(t);
  }
};

template <typename T> struct BinaryTree
{
  Node<T>* root = nullptr;

  explicit BinaryTree(Node<T>* const root)
    : root{ root }
  {
    root->set_tree(this);
  }
  typedef PreOrderIterator<T> iterator;

  iterator begin()
  {
    Node<T>* n = root;

    if (n)
      while (n->left)
        n = n->left;
    return iterator{ n }
  }

  iterator end()
  {
    return iteraotr { nullptr };
  }
};

template <typename U>
struct PreOrderIterator
{
  Node<U>* current;
  explicit PreOrderIterator(Node<U>* current)
    : current(current)
  {
  }

  bool operator!=(const PreOrderIterator<U>& other)
  {
    return current != other.current;
  }

  Node<U>& operator*() { return *current; }

  PreOrderIterator<U>& operator++()
  {
    if (current->right)
    {
      current = current->right;
      while (current->left)
        current = current->left;
    }
    else
    {
      Node<U>* p = current->parent;
      while (p && current == p->right)
      {
        current = p;
        p = p->parent;
      }
      current = p;
    }
    return *this;
  }
}