An In-Order Iterator

In this development phase, you'll implement the read-only iterator for trees (a class TreeStringSet::ConstIter, provided to users as TreeStringSet::const_iterator) that accesses the tree in sorted order. Our iterator only provides read-only access because modifying the tree items could change their relative ordering and result in an invalid tree.

Once you have the iterator written, you'll be able to write code like

// Output tree in sorted order, one item per line
for (const std::string& item : myTree) {
    std::cout << item << std::endl;
}

The public const_iterator type is implemented by a private ConstIter class, which you will be writing.

Background: In-Order Traversal of a BST

Your iterator will need to perform an in-order traversal of your tree. Writing an iterator for a non-linear data structure like a tree is bit more complicated than writing an iterator for a linear data structure like a linked list. In Homework 5, your iterator only needed to know which Node it was “at” in the linked list to have all of the information it needed to know where it should go next—it had a Node* member variable that kept track of the Node it was “at”. For a tree, that kind of approach wouldn't be sufficient—if we just had a single Node* variable, when we got down to a leaf we'd be stuck with no way to go to the next node in order (remember, our trees don't have parent pointers). Our tree iterator will need to store more information to navigate its way through the tree.

Before working out how our iterator should be coded to perform an in-order traversal, let's first look at how we might implement in-order-traversal as a single function. The most common way of specifying such a traversal is recursively. Here's the pseudocode:

IN-ORDER-PRINT(subtree):
    if subtree is empty:
        return
    else:
        IN-ORDER-PRINT(subtree→lhs)
        PRINT(subtree→key)
        IN-ORDER-PRINT(subtree→rhs)

While it is fairly straightforward to trace through this recursive code with a tree and see that it prints out the nodes in order, it may not be easy to see how to make an iterator that would visit the values in the same order. The trick is to first realize that any recursive algorithm that uses the C++ stack and recursion can be converted to non-recursive code that uses a stack data structure.

We've converted the above code into a nonrecursive version of the same algorithm, and this version will be a more helpful starting point for making our iterator:

IN-ORDER-PRINT(subtree):
    create a  stack (of node pointers), s
    starting at root of subtree follow the leftward path down to the minimum, pushing the nodes onto the stack, s
    while stack s is not empty:
        PRINT(TOP(s)→key)
        let oldtop = POP(s)
        starting at right child of oldtop follow the leftward path down to the minimum, pushing the nodes onto the stack, s

We've color-coded the pseudocode: highlighting shows the encoding; dark violet shows initialization; blue shows reading the value at the current position; green shows moving to the next element; and orange shows the state when we're done (i.e., have run off the end of our tree).

Notice that the part about pushing all the nodes on the leftward path down to the (subtree's) minimum value appears twice, so it could be split out as a helper function PUSH-TO-MINIMUM(stack, subtree).

From Nonrecursive Code to an Iterator

We can break the above function into pieces to create our iterator:

• Encoding: stack (of node pointers), s.
• Construct Starting Iterator: create a stack, s; PUSH-TO-MINIMUM(s, root-of-the-tree).
• Construct Past-the-End Iterator: Make a stack, s, that is empty.
• Read Item at Current Position: TOP(s)→key.
• Advance to Next Item: let oldtop = POP(s); PUSH-TO-MINIMUM(s, oldtop→rhs).

Your Task

Using the description above, and following the four steps of our development process (Plan, Write Tests, Implement, Test & Fix), implement the in-order iterator.

You will need to write

• begin() and end() for TreeStringSet.
• Any private (and static) helper functions, such as a pushToMinimum() function.
• All the member functions of your TreeStringSet::ConstIter.

The necessary functions are described in the TreeStringSet Specification.

Designing and Implementing Your Iterator

The fundamental design of the iterator, from the encoding to the functions themselves, is already given above, where color-coding calls out the different parts of the iteration process. However, that description is in informal English, and you need to translate it into C++ code.

While we’ve put implementing all of these functions into one phase, we strongly encourage you to break the coding process into smaller pieces, and to go through the planning, test writing, implementation, and verification steps for each smaller set of functions. For example, you might break them down into

• Constructors, assignment operator, destructor
• begin(), end(), operator*
• operator++
• operator== and operator!=

Planning for the Encoding of Your Iterator

As noted above, your iterator needs to store a stack of Node pointers. The top of the stack is the current node, and other elements are yet-to-be-visited parents of that node.

The C++ standard library provides several possible data structures you could use for your stack data structure. The type std::stack is the most obvious choice (use push(), pop(), top(), and ==), but another viable option is std::forward_list (use push_front(), pop_front(), front(), and ==).

To be able to use a std::stack, you should #include the <stack> header. You can then define a data member that is a stack of whatever type of value you want to hold. For example, to declare a stack of Node pointers, you might write

std::stack<Node*> stack_;

The begin() Iterator

begin() should return a ConstIter that is “at” the the minimum element of the tree, and have all of its parents pushed onto the stack (with the tree's root pushed first, ending up at the very bottom). Use a helper function for this aspect.

The end() Iterator

The end iterator has an empty stack. How you make the end iterator is up to you. You may be able to use the same constructor you used with begin() or the default constructor for your iterator.

Advancing the Iterator

See above, but, essentially,

• Save the Node* at the top of the stack.
• Pop off the top node of the stack.
• Push the path to the minimum value of the right subtree of the old top node. (Use a helper function!)

Comparing Two Iterators

• Two iterators should be equal only if they are “at” the same Node (i.e., the same Node* at the top of the stack) and they have the same stack of Node*s left to visit—in other words, they are equal if their stacks are equal.
• Two default-constructed iterators should also be equal (in order to comply with the most recent C++ standard).

You can test whether two stacks are the same (==) using the overloaded operator== comparator.

Debugging Your Iterator

If you need to debug your iterator, here's some debugging output from running this code (which uses our iterator),

for (std::string key : myTree) {
    std::cout << ">>> " << key << " <<<" << std::endl;
}

to print out a tree.

This loop is run on three different trees with the elements ‘A’…‘O’, once with them in sorted order (making a stick); again, with them in reverse order (also making a stick); and finally with them in an order that would make a perfectly balanced tree. We've added debugging output to show stack push()es, pop()s, and calls to top().

┌────────────────────────┬────────────────────────┬────────────────────────┐
│ Tree: ABCDEFGHIJKLMNO  │ Tree: ONMLKJIHGFEDCBA  │ Tree: HDLBFJNACEGIKMO  │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ - push(A)              │ - push(O)              │ - push(H)              │
│ - top() [read A]       │ - push(N)              │ - push(D)              │
│ >>> A <<<              │ - push(M)              │ - push(B)              │
│ - pop() [popped A]     │ - push(L)              │ - push(A)              │
│ - push(B)              │ - push(K)              │ - top() [read A]       │
│ - top() [read B]       │ - push(J)              │ >>> A <<<              │
│ >>> B <<<              │ - push(I)              │ - pop() [popped A]     │
│ - pop() [popped B]     │ - push(H)              │ - top() [read B]       │
│ - push(C)              │ - push(G)              │ >>> B <<<              │
│ - top() [read C]       │ - push(F)              │ - pop() [popped B]     │
│ >>> C <<<              │ - push(E)              │ - push(C)              │
│ - pop() [popped C]     │ - push(D)              │ - top() [read C]       │
│ - push(D)              │ - push(C)              │ >>> C <<<              │
│ - top() [read D]       │ - push(B)              │ - pop() [popped C]     │
│ >>> D <<<              │ - push(A)              │ - top() [read D]       │
│ - pop() [popped D]     │ - top() [read A]       │ >>> D <<<              │
│ - push(E)              │ >>> A <<<              │ - pop() [popped D]     │
│ - top() [read E]       │ - pop() [popped A]     │ - push(F)              │
│ >>> E <<<              │ - top() [read B]       │ - push(E)              │
│ - pop() [popped E]     │ >>> B <<<              │ - top() [read E]       │
│ - push(F)              │ - pop() [popped B]     │ >>> E <<<              │
│ - top() [read F]       │ - top() [read C]       │ - pop() [popped E]     │
│ >>> F <<<              │ >>> C <<<              │ - top() [read F]       │
│ - pop() [popped F]     │ - pop() [popped C]     │ >>> F <<<              │
│ - push(G)              │ - top() [read D]       │ - pop() [popped F]     │
│ - top() [read G]       │ >>> D <<<              │ - push(G)              │
│ >>> G <<<              │ - pop() [popped D]     │ - top() [read G]       │
│ - pop() [popped G]     │ - top() [read E]       │ >>> G <<<              │
│ - push(H)              │ >>> E <<<              │ - pop() [popped G]     │
│ - top() [read H]       │ - pop() [popped E]     │ - top() [read H]       │
│ >>> H <<<              │ - top() [read F]       │ >>> H <<<              │
│ - pop() [popped H]     │ >>> F <<<              │ - pop() [popped H]     │
│ - push(I)              │ - pop() [popped F]     │ - push(L)              │
│ - top() [read I]       │ - top() [read G]       │ - push(J)              │
│ >>> I <<<              │ >>> G <<<              │ - push(I)              │
│ - pop() [popped I]     │ - pop() [popped G]     │ - top() [read I]       │
│ - push(J)              │ - top() [read H]       │ >>> I <<<              │
│ - top() [read J]       │ >>> H <<<              │ - pop() [popped I]     │
│ >>> J <<<              │ - pop() [popped H]     │ - top() [read J]       │
│ - pop() [popped J]     │ - top() [read I]       │ >>> J <<<              │
│ - push(K)              │ >>> I <<<              │ - pop() [popped J]     │
│ - top() [read K]       │ - pop() [popped I]     │ - push(K)              │
│ >>> K <<<              │ - top() [read J]       │ - top() [read K]       │
│ - pop() [popped K]     │ >>> J <<<              │ >>> K <<<              │
│ - push(L)              │ - pop() [popped J]     │ - pop() [popped K]     │
│ - top() [read L]       │ - top() [read K]       │ - top() [read L]       │
│ >>> L <<<              │ >>> K <<<              │ >>> L <<<              │
│ - pop() [popped L]     │ - pop() [popped K]     │ - pop() [popped L]     │
│ - push(M)              │ - top() [read L]       │ - push(N)              │
│ - top() [read M]       │ >>> L <<<              │ - push(M)              │
│ >>> M <<<              │ - pop() [popped L]     │ - top() [read M]       │
│ - pop() [popped M]     │ - top() [read M]       │ >>> M <<<              │
│ - push(N)              │ >>> M <<<              │ - pop() [popped M]     │
│ - top() [read N]       │ - pop() [popped M]     │ - top() [read N]       │
│ >>> N <<<              │ - top() [read N]       │ >>> N <<<              │
│ - pop() [popped N]     │ >>> N <<<              │ - pop() [popped N]     │
│ - push(O)              │ - pop() [popped N]     │ - push(O)              │
│ - top() [read O]       │ - top() [read O]       │ - top() [read O]       │
│ >>> O <<<              │ >>> O <<<              │ >>> O <<<              │
│ - pop() [popped O]     │ - pop() [popped O]     │ - pop() [popped O]     │
└────────────────────────┴────────────────────────┴────────────────────────┘

(When logged in, completion status appears here.)