Comparison of the Approaches to the Traversal of a Binary Tree Structure Using Iterators

The tree (hierarchical) structure is one of the elementary memory arrangements, used by numerous data structures – ranging from simple to relatively sophisticated ones. The most well-known tree structure is probably the binary tree. Such a tree is the basis for efficient implementations of (binary) search trees. In addition to the typical search tree operations like find, insert, and remove, the operation of tree traversal that sequentially accesses all elements is also very important. Typically, the traversal is implemented using a dedicated object called iterator. The paper deals with different ways of implementing a binary tree iterator. The main contribution of the paper is an experimental comparison of various implementations of the iterator. The comparison shows that the simple straightforward approach is unequivocally the fastest.