**Data Structures- Trees, Stacks, and the Iterator Pattern**

In this tutorial, we will be shifting gears from recursion to implementing an Iterator for a Tree. If you haven't already done so, I would highly recommend reading up on my previous tutorial on Recursion, Stacks, and Trees, as it covers a lot of the foundation for the Iterator Pattern here. The reason for this shift is because implementing an Iterator for a Tree nicely ties together a lot of the concepts we have talked about with Stacks and Tree Models. In addition, designing an Iterator is a key part of implementing the Collection interface, and this is not necessarily the most straight-forward for Trees like it is for Lists and Sets. Also, the concepts presented in this tutorial are applicable to Tree parsing in general.

So to start, we will want to have our Iterator calss implementing the Iterator interface which accepts the Tree it will be iterating over in the constructor. Just like the Call Stack is the underlying structure for when we utilize recursion, a Stack will be the backbone of our Iterator. However, I will be using a custom Stack implementation- a StackMap. Specifically, I will be storing a StackMap<TreeNode<E>, Integer> so I can control the iteration through the Tree. With recursion, calls are pushed onto the Call Stack, then popped off when the call completes. The StackMap allows us to better control when Nodes are pushed and popped for iteration with the Iterator. For specific information on the StackMap, see my StackMap snippet.

class TreeIterator<E> implements Iterator<E>{ //used to store TreeNodes in depth-first ordering //as well as their positions in the parent TreeNode private StackMap<TreeNode<E>, Integer> callStack; //the Tree we are iterating over private Tree<E> tree; //used to flag that another element has been returned //and prevent the remove() method from trying to remove the //same element twice private boolean returnedNext; //used to flag that the iteration has been started //to differentiate between when the StackMap is empty //after the Tree has been completely traversed private boolean returnedRoot; public TreeIterator(Tree<E> tree){ this.tree = tree; callStack = new StackMap<TreeNode<E>, Integer>(); returnedNext = true; returnedRoot = false; } //the Iterator methods we will be implementing public boolean hasNext(){} public E next(){} public void remove(){} }

Now let's outline our logic some before beginning. To start, we will push the root Node onto the StackMap when we instantiate the Iterator. When the next() method is called, the current element on the StackMap will be returned, and the next element will be pushed onto the Stack in depth-first order. When a Node has no more children to be pushed onto the Stack (ie., we have hit the bottom), it will be popped from the StackMap and go back upto the parent Node.

So how will the hasNext() method work? Basically, it checks to see if the Stack is empty to determine whether or not there is another element. Remember, we push an element onto the StackMap, then return that element when next() is called. So by the time the StackMap is empty, we have traversed the entire Tree.

//There are more elements to iterate through iff the Stack isn't empty //Otherwise, we have traversed through all the elements in the Tree public boolean hasNext(){ return !(callStack.isEmpty() && returnedRoot);}

The next() method utilizes the StackMap data structure to back the Iterator. Basically, we start by pushing the root Node onto the StackMap. On each subsequent call of next(), we examine the top element on the StackMap. If it has children, then we push its first child onto the CallStack. If the top element doesn't have any more children, then we pop it and go to the next element on the StackMap. We repeat this process until we find a Node that has more children, or until we have run through all the elements on the StackMap.

/** * @return: The next element in the Tree, null if there are no more elements **/ public E next(){ //if there isn't another element to iterate over //then return null if(!hasNext()) return null; //otherwise, flag that we've returned the next //element in the Tree returnedNext = true; /*** * if the callStack is empty and we haven't pushed the * root Node already (hasNext() takes this into account) * then we will push the root Node and mark that we have done so * as to prevent iterating over the Tree multiple times with one * Iterator ***/ if(callStack.isEmpty()){ callStack.push(tree.getRoot(),0); returnedRoot = true; } //otherwise else{ //start by examining the current element TreeNode<E> temp = callStack.peek().getKey(); int value = callStack.peek().getValue(); //if it has a child Node, then push it onto the callStack if(temp != null && temp.numberChildren() > 0) callStack.push(temp.get(0),0); //otherwise, go up levels in the callStack until we hit a Node that has another //child to add else{ callStack.pop(); temp = callStack.peek().getKey(); while(value >= temp.numberChildren()-1 && callStack.size() > 1){ value = callStack.pop().getValue(); temp = callStack.peek().getKey(); } if(!callStack.isEmpty() && value < temp.numberChildren()-1){ callStack.push(temp.get(value+1), value+1); } //if we get to the root Node, we've traversed the entire tree //so we flag returnedNext as false so remove() won't do anything //and return null, as there are no more elements to iterate over else if(temp == tree.getRoot() && returnedRoot){ returnedNext = false; return null; } } } //end else return callStack.peek().getKey().getValue(); }

As for the remove() method, what it does is remove the element last returned by next() from the Tree. It starts by examining the top element on the StackMap, popping it from the StackMap. We then remove any children from that Node, and remove that Node from the current StackMap's head element. This is very similar to removing an element from a Linked List. We then push the element we popped back onto the CallStack, decrementing its value by 1 to compensate for the fact that it is no longer in the Tree. We do this, as the next() method will then process this element normally and proceed onto the next element in the Tree.

The special case we have is when we try to remove the root Node of the Tree. When this happens, we just clear the Tree and the StackMap.

public void remove(){ //if we haven't returned another element from next() //or there aren't any more elements in the callStack //then terminate this method call if(!returnedNext || callStack.isEmpty()){ return; } //if the element we are trying to remove is the Root //of the Tree, then we'll just clear the Tree and the //callStack if(callStack.peek().getKey() == tree.getRoot()){ tree.clear(); callStack.pop(); } //otherwise else{ //pop the top element and get the current its value TreeNode<E> temp = callStack.peek().getKey(); int value = callStack.pop().getValue(); //remove the element we popped from the Tree callStack.peek().getKey().remove(temp); //and remove its children so they won't be //returned by the next() method temp.getConnections().clear(); //now push it back onto the callStack //decrementing its value to account for the fact //that its former parent Node now has one fewer children callStack.push(temp, value-1); } returnedNext = false; }