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

Question

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 <typename T>
struct Node {
 Node(T content);
 virtual ~Node() = default;
 /** Get the object stored in the node */
 T& getContent();
 /** Pointers to construct the tree */
 Node<T> *leftChild, *rightChild, *parent;
 /** Content stored in the node */
 T content;
};

Member-Definitions

template <typename T>
RBNode<T, K>::RBNode(T content)
 : leftChild(nullptr)
 , rightChild(nullptr)
 , parent(nullptr)
 , content(content) {
}
template <typename T>
T& RBNode<T, K>::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 <typename T>
class Tree;
template <typename T>
struct Node;
template <typename T>
class TreeIterator {
 friend class Tree<T>;
public:
 TreeIterator(const Tree<T>* instance, Node<T>* initialNode);
 TreeIterator(const TreeIterator&);
 TreeIterator(TreeIterator&&);
 ~TreeIterator() = default;
 TreeIterator<T>& operator=(const TreeIterator<T>&);
 TreeIterator<T>& operator=(TreeIterator<T>&&);
 TreeIterator<T>& operator++();
 TreeIterator<T> operator++(int);
 T& operator*();
 T* operator->();
 const T* operator->() const;
 Node<T>* node();
 bool operator==(const TreeIterator<T>&) const;
 bool operator!=(const TreeIterator<T>&) const;
 /** Used by the tree to generate begin() iterator */
 static TreeIterator<T> begin(Tree<T>* instance, Node<T>* rootNode);
private:
 const Tree<T>* instance;
 Node<T>* currentNode;
};

Constructors and Assignment

template <typename T>
TreeIterator<T>::TreeIterator(const Tree<T>* instance, Node<T>* initialNode)
 : instance(instance)
 , currentNode(initialNode) {
}
template <typename T>
TreeIterator<T>::TreeIterator(const TreeIterator& other)
 : instance(other.instance)
 , currentNode(other.currentNode) {
}
template <typename T>
TreeIterator<T>::TreeIterator(TreeIterator&& other)
 : instance(other.instance)
 , currentNode(other.currentNode) {
 other.instance = nullptr;
 other.currentNode = nullptr;
}
template <typename T>
TreeIterator<T>& TreeIterator<T>::operator=(const TreeIterator<T>& other) {
 this->instance = other.instance;
 this->currentNode = other.currentNode;
 return *this;
}
template <typename T>
TreeIterator<T>& TreeIterator<T>::operator=(TreeIterator<T>&& other) {
 this->instance = other.instance;
 this->currentNode = other.currentNode;
 other.instance = nullptr;
 other.currentNode = nullptr;
 return *this;
}

---

-> ITERATING <-

The iterator uses the parent and the leftChild and rightChild pointers to traverse the tree. Since the relation between two connected nodes is always evident and since there are no loops, it is possible to iterate over the nodes without requiring additional memory.

/*
 * iterate over a Tree in postorder
 */
template <typename T>
TreeIterator<T>& TreeIterator<T>::operator++() {
 Node<T>* parent;
 if(this->currentNode == nullptr) {
 /* '-> end iterator does not increment */
 return *this;
 }
 parent = this->currentNode->parent;
 /*
 * reaches root -> next is end()
 */
 if(parent == nullptr) {
 this->currentNode = nullptr;
 return *this;
 }
 /*
 * left child -> go to right child
 * right child -> go to parent
 */
 if((this->currentNode == parent->leftChild) && (parent->rightChild != nullptr)) {
 this->currentNode = parent->rightChild;
 } else {
 this->currentNode = this->currentNode->parent;
 return *this;
 }
 while(true) {
 if(this->currentNode->leftChild != nullptr) {
 /* '-> has left child node */
 this->currentNode = this->currentNode->leftChild;
 } else if(this->currentNode->rightChild != nullptr) {
 /* '-> only right child node */
 this->currentNode = this->currentNode->rightChild;
 } else {
 /* '-> has no children -> stop here */
 return *this;
 }
 }
}
template <typename T>
TreeIterator<T> TreeIterator<T>::operator++(int) {
 TreeIterator<T> old = *this;
 ++(*this);
 return old;
}

Other Member-Definitions

template <typename T>
T& TreeIterator<T>::operator*() {
 return this->currentNode->getContent();
}
template <typename T>
T* TreeIterator<T>::operator->() {
 return &(this->currentNode->getContent());
}
template <typename T>
const T* TreeIterator<T>::operator->() const {
 return &(this->currentNode->getContent());
}
template <typename T>
Node<T>* TreeIterator<T>::node() {
 return this->currentNode;
}
template <typename T>
bool TreeIterator<T>::operator==(const TreeIterator<T>& other) const {
 return (this->instance == other.instance && this->currentNode == other.currentNode);
}
template <typename T>
bool TreeIterator<T>::operator!=(const TreeIterator<T>& other) const {
 return !((*this) == other);
}
template <typename T>
TreeIterator<T> TreeIterator<T>::begin(Tree<T>* instance, Node<T>* rootNode) {
 if(rootNode == nullptr) {
 return TreeIterator(instance, rootNode);
 }
 /*
 * iterate to the node in the bottom-left
 */
 while(true) {
 if(rootNode->leftChild != nullptr) {
 rootNode = rootNode->leftChild;
 } else if(rootNode->rightChild != nullptr) {
 rootNode = rootNode->rightChild;
 } else {
 return TreeIterator(instance, rootNode);
 }
 }
}

---

Questions

• Have I missed anything important about implementing iterators? Are there style flaws?
• Since large parts of the tree can change during an add() or remove() operation, these operations may not be performed while iterating over the tree, because the active iterator might skip elements or visit them multiple times. Is this also the case for STL iterators of standard containers?
  • If not, is there a way to make my iterator more robust against changes in the tree structure?

You can also have a look at the complete implementation including the Red-Black-Tree at this GitHub repository.

• Emily L.: Welcome to code review, your question looks very good and I hope you get done nice answers.

Answer 1

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<T>& operator=(TreeIterator<T>&&);

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

TreeIterator<T>& operator++();
TreeIterator<T> 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".

• Maximilian Köstler: Thanks for the analysis! The passing by value in the Node constructor was well spotted. I actually just missed that. You are also right about my const-correctnes... It seems like I've been sloppy on this one. I will also add a swap()-function for my iterator. Regarding the default-constructability: Is the default-constructed iterator just supposed to point to nothing? In that case appying operator*() to that iterator will of cause fail. As stated in my post, there is no STL on my target plaform. Thereby there is no std::iterator_traits, so I guess I will just leave that. Thanks again!
• Loki Astari: The default constructed "forward iterator" is supposed to represent end. See istream_iterator for an example.
• Loki Astari: PS. I would still add the reference and value_type to your object. These can come in useful.