Comparison of various in-order iterator implementations in C++

Abstract Data structures typically use sequential or hierarchical arrangements of elements. Hierarchical data structures are commonly referred to as trees. Trees can be implemented and applied in various ways from simple to relatively sophisticated structures. Undoubtedly, the most well-known tree structure is the binary tree. Such a tree is essential for efficient implementations of (binary) search trees, which typically provide operations like find, insert, and remove. In addition to these, the operation of tree traversal – that sequentially accesses all the elements – is also very important. Data structure libraries mostly implement traversal using the iterator design pattern. The article examines different approaches to implementing an iterator for a binary tree. The article’s main contribution lies in an experimental comparison of various iterator implementations. The comparison also includes an AI-generated iterator. The results show that the simple, straightforward approach commonly used in standard libraries is the fastest and that the AI-generated iterator performs reasonably well.