Implementing C++ Iterators in Binary Search Trees with Parent Pointers

mgcadmin 23-04-2023

My past two articles dealt with deleting items from an AVL tree in C++ and linked list iterators in java. So I figured I would let the two paths cross in this article by covering forward iterators for AVL trees using the STL style of the iterator pattern. If you haven't ready my previous two posts on constructing AVL trees, I would recommend reading them first as the code in this post builds off of those two posts.

STL style iterators

Where java uses methods to interact with iterator objects, C++ employs operator overloading. Nevertheless, the process is very similar. Our iterator object will require an entry point into the tree in the form of a reference to a node. What a forward iterator is actually doing under the hood is a stack-less, iterative, in order traversal of the underlying tree. This is possible thanks to our use of parent pointers in the AVL tree, otherwise some form of additional memory such as a stack would be required.

The firs step is designing our iterator object, and already we are faced with a design decision: Do we make our iterator class a nested class of the AVLTree class, or make it a friend class. Personally, I like the idea of a nested class for an iterator, but the choice is yours: keep in mind when using a nested class that it should be defined public. Just as it was with linked lists, an iterator to binary search tree is little more than a wrapper around an individual node: the node currently being visited, with associated methods for transitioning to the next node:

template <class T, class T2>
class AVLTree {
    private:
        typedef pair<T,T2> entry;
        struct node {
            entry data;
            int height;
            node* left;
            node* right;
            node* parent;
            node(entry p) {
                data = p; height = 0; left = right = parent = nullptr;
            }
        };
    public:
        class AVLIterator {
            private:
                node* curr;
            public:
                AVLIterator(node* c) {
                    curr = c;
                }
   /*    code continues... */

Immediately you can see how the iterator pattern helps us to hide the implementation of our tree, by allowing us to keep the node structure private, whole only exposing an iterator as an indirect reference to said node. To make our iterator useful as well as conform to how they are used in the STL. Any C++ iterator implementation must have operator==, oeprator!=, as well as operator* defined so that they can be compared, and the data from the node being referenced can be retrieved.

 /*    code continues... */
         entry& operator*() {
                return curr->data;
         }
  
        bool operator==(const AVLIterator& o) const {
             return this->curr == o.curr;
        }
        bool operator!=(const AVLIterator& o) const {
             return !(*this==o);
        } 

/*   code continues.... */  

With all that we are finally ready to make our iterators... iterate. The defining property of a binary search tree is that an inorder traversal of its nodes yields that data contained with in in ascending sorted order. Thus, it only makes sense that our iterator takes advantage of that fact to also traverse our tree in sorted order, as it does in std::map and std::set. This can be accomplished in a number of ways. One common way is to use a stack to perform an iterative inorder traversal of the tree, but as mentioned above, having used parent pointers, we can do not have to deal with maintaining an additional stack. Parent pointers allow efficient "find predecesssor" and "find successor" operations. So if our iterator begins its traversal by having its current node point to the left most node in the tree, all wehave to do is keep finding the next in order successor, and reassigning curr to point to that node. This is the strategy employed by the implementation of operator++:

/*   code continues.... */ 
                AVLIterator& operator++() noexcept {
                   node* p;
                    if (curr->right != nullptr) {
                        curr = curr->right;
                        while (curr->left != nullptr) curr = curr->left;
                    } else {
                        p = curr->parent;
                        while (p != nullptr && curr == p->right) {
                            curr = p;
                            p = p->parent;
                        }
                        curr = p;
                    }
                   return *this;
                } 

/*   code continues.... */  

And we have to define both pre- and post-increment operators:

 /*   code continues.... */ 
 
               AVLIterator operator++(int) noexcept {
                    AVLIterator it = *this;
                    ++*this;
                    return it;
                } 

 
/*   code continues.... */  

To ensure our iterator is working as intended lets code up a little example that does two things: insert the characters of a string as the keys into our avl tree, perform a standard recursive inorder traversal of the tree, and then use our iterator object to do the same:

 int main() {
    AVLTree<char, char> avl;
    string sed = "aniteratorexample";
    for (char c : sed)
        avl.insert(c, c);
    avl.sort();
    for (AVLTree<char, char>::AVLIterator it = avl.begin(); it != avl.end(); it++) {
        cout<<(*it).first<<" ";
    }
    return 0;
}  

max@MaxGorenLaptop:/mnt/c/Users/mgoren$ g++ avlclient.cpp -o avlclient
max@MaxGorenLaptop:/mnt/c/Users/mgoren$ ./avlclient
 a a a e e e i l m n o p r r t t x 
 a a a e e e i l m n o p r r t t x
max@MaxGorenLaptop:/mnt/c/Users/mgoren$

Et voila! we have a working forward iterator for our AVL Tree. The functins begin() and end() in AVLTree are implemented as follows:

 /*   code continues... */
        AVLIterator begin() noexcept {
            return AVLIterator(min(root));
        }
        AVLIterator end() {
            return AVLIterator(nullptr);
        } 

 /*   code continues... */ 

A reverse iterator, and indeed operator-- could be implemented in a similar way but in reverse. I will leave that as an exercise for the reader. Until next time, Happy hacking!

A fully working implementation of my AVL Tree with iterators can be found on my github at: https://github.com/maxgoren/AVLDict

 

---