Please fill out this survey: rit.az1.qualtrics.com/jfe/form/SV_e8oGJ4NqeXgVblX

Use this GitHub Classroom link to get started: classroom.github.com/a/nzzZpIsq.

The challenge:

Add iterators to the Binary Search Tree code from the Weiss text. Specifically, you will add const and "regular" iterator classes with the following public methods:

const_iterator

• Constructors as needed.
• const_iterator& operator++()
• bool operator==(const const_iterator &other) const
• Comparable& retrieve() const
  (Used by the various operator*() methods

iterator

• Constructors as needed
• (The other methods are already inherited from const_iterator.)

BinarySearchTree

• const_iterator cbegin() const
  Return a constant iterator pointing to thesmallest node in the tree.
• const_iterator end() const
  Return a constant iterator signifying the end.
• const_iterator cfind(const Comparable &item) const
  Return a constant iterator pointing to the the node with value item. If item does not appear in the tree, return thecend pointer.
• iterator begin()
  Return a "regular" iterator pointing to the smallest node in the tree.
• iterator end()
  Return a "regular" iterator signifying the end.
• iterator find(const Comparable &item) const
  Return a "regular" iterator pointing to the the node with value item. If item does not appear in the tree, return theend pointer.

Rules

Important: You may not modify the BinaryNode structure. Your iterator must mantain all the necessary data to navigate the tree. We don't want to add previous, next, and/or parent pointers to the nodes, because that would add O(n) additional space to the tree. Instead, your iterator need only maintain O(h) data, where h is the height of the tree.

Suggestions

• Write (and test) the const iterator first. (You can run the tests for only the const iterator by passing "const*" as a parameter to the test file.)
• Your "regular" iterator should inherit from your const iterator. If you do this, you need only implement the constructors. The other const iterator methods can be used without any changes.
• Sketch a variety of trees to use as test cases.

Submission and grading

• Please make sure your name appears in all source code files.
• Please fill out this survey (optional): rit.az1.qualtrics.com/jfe/form/SV_e8oGJ4NqeXgVblX
• Make sure all relevant code (including unit tests) is checked in to GitHub by the due date.
• Unless you indicate otherwise, I will assume that the code to be graded is on the master branch.
• You are expected to fix and re-submit buggy code. Because your code will eventually be correct, your grade will be based primarily on timeliness.

Updated Friday, 15 November 2019, 7:26 AM