Iterator through binary trees (with parent-pointer) without memory-overhead

I have been working on a custom Tree class that enforces certain rules upon insertion and deletion.
The implemented tree is a Red-Black-Tree but since the implementation is far too long, I will not post the complete code but only the relevant parts. I have also reduced the code and removed the Red-Black-Tree specific parts such as the colour that each node usually has to store.

This question is not about the tree itself, but about its iterator.

Note that I can not use any elements from the STL such as shared_ptr or unique_ptr on my target platform.

Tree Nodes

This struct represents the nodes of the tree and since I implemented a Red-Black-Tree, each node already has a pointer to its parent. This will be used later for iterating the tree without recursion and without an extra stack.

Member-Declarations

template 
struct Node {
    Node(T content);
    virtual ~Node() = default;

    /** Get the object stored in the node */
    T& getContent();

    /** Pointers to construct the tree */
    Node *leftChild, *rightChild, *parent;

    /** Content stored in the node */
    T content;
};

Member-Definitions

template 
RBNode::RBNode(T content)
  : leftChild(nullptr)
  , rightChild(nullptr)
  , parent(nullptr)
  , content(content) {
}

template 
T& RBNode::getContent() {
    return content;
}

Tree-Iterator

The interesting part of the Implementation is the iterator I use to traverse the tree. It is important that it iterates in post-order, so that during the destruction of the tree I can use this iterator to delete all nodes by simply iterating over them.

Member-Declarations

```
template
class Tree;

template
struct Node;

template
class TreeIterator {
friend class Tree;

public:
TreeIterator(const Tree instance, Node initialNode);

TreeIterator(const TreeIterator&);

TreeIterator(TreeIterator&&);

~TreeIterator() = default;

TreeIterator& operator=(const TreeIterator&);
TreeIterator& operator=(TreeIterato

Node

Constructor: Seem to take the object to be stored by value. This may cause an extra copy. Pass the object by reference:

Node(T const& content);

That way you don't copy the parameter just make a copy into the new object. Also you may want to look at the opertunity of moving the object into the node.

Node(T&& content) noexcept;

Additionally with the addition of template varargs the use of emplace to create the data object in place using parameters is always an option.

template<typename... Args)
Node(Args&& args);

Const correctness

This is fine:

T& getContent();

But what if your object is used in const context (ie you pass your tree to a function and the parameter is a const reference). You can now no longer use this method. You may want to add a const version of this method so that you can accesses the data object in a const context.

T const& getContent() const;

Iterator

The iterator object is supposed to be a very cheap object to maintain and copy. As a result it feels strange to have a move operator. I don't think you will find many people move iterators around.

TreeIterator(TreeIterator&&);
TreeIterator& operator=(TreeIterator&&);

You allow increment but not decrement. So this is a forward iterator only.

TreeIterator& operator++();
TreeIterator operator++(int);

I see a normal iterator and thus normal access. You usually also want a const iterator with const accesses to the data. I see that you give const version of operator-> but not operator*.

T& operator*();
T* operator->();
const T* operator->() const;

Missing functionality:

You implemented a "ForwardIterator" this means you need to fulfill the requirements of "Iterator"/"Input Iterator"/"Forward Iterator". The things you missed

Iterator

http://en.cppreference.com/w/cpp/concept/Iterator

One of the requirements of an iterator is that it is swapable. You don't seem to have done this part:

Input Iterator

http://en.cppreference.com/w/cpp/concept/InputIterator

• reference, the type denoted by std::iterator_traits::reference

• value_type, the type denoted by std::iterator_traits::value_type

Forward Iterator

http://en.cppreference.com/w/cpp/concept/ForwardIterator

The iterator should be "Default Constructable".

StackExchange Code Review Q#153476, answer score: 4