Binary Search tree inorder iterator next method

Question

I'm building a Binary Search Tree class that has an inorder iterator and a pre-order iterator. I've coded up an attempt for the inorder iterator but I don't think I have this code right. I read some guides on coding the iterators and I took what I interpreted and tried to implement it in my design. The hasNext that is returning the tree is questionable. Currently the tree.isEmpty() returns whether the root node is null for the tree. I'm not sure if that's correct to check during an iteration of the tree.

I'm not entirely confident in my understanding of how Inorder iteration works. Currently, I'm starting at root.left with the next() method than attempting to iterator from there.

Some Notes for code clarification E = element / data for the nodes K = key

public class BSTIterator<E, K> implements StructureIterator<E> {

    private final BST<E, K> tree;
    BSTNode<E> root =null;
//    Comparator<E> sortFct;
//    BiFunction<K, E, Integer> searchFct;

    public BSTIterator( BSTNode<E> root,Comparator<E> sortFct,
                        BiFunction<K, E, Integer> searchFct) {
        this.tree = new BST<E, K>(sortFct, searchFct);
        this.root = root;
    }

    @Override
    public E next() {
        BSTNode<E> node = tree.root.getLeft();
        E result = node.getData();
        if(node.getRight() != null){
            while(node != null){
                tree.root.getRight();
                node = node.getLeft();
            }
        }
        return result;
    }

    @Override
    public boolean hasNext() {
        return !tree.isEmpty();
    }
}

Glains Glains · Accepted Answer · 2020-12-07T18:52:07

First of all, inspect constructor. Iterators should be fast and usually use a live copy of the underlying data structure. Therefore, i would recommend to not create a new tree every time.

public BSTIterator(BST<E, K> tree) {
    this.currentNode = tree.getRoot();
}

Now, to iterate through a tree structure without using recursion, you can use a Stack. Also, keep track of the currently visited node.

Stack<BSTNode<E>> stack = new Stack<>();
BSTNode<E> currentNode;

Now, the next() method. To start, make sure to throw a NoSuchElementException if there are no more elements left for the current iterator. We will simply use !hasNext() for now. Then you follow the steps:

Push nodes to the stack until the current node does not have a left child.
If the currentNode is null and the Stack is not empty, pop() a node, update currentNode to the right child and return the contained node data. The next time you call next(), traversal will continue at this position.
If the currentNode is null and the stack is empty, you are done.

This is the implementation of the next():

@Override
public E next() {
    if(!hasNext())
        throw new NoSuchElementException();

    while(!stack.empty() || currentNode != null) {
        if(currentNode != null) {
            stack.push(currentNode);
            currentNode = currentNode.getLeft();
        } else {
            BSTNode<E> node = stack.pop();
            currentNode = node.getRight();
        
            return node.getData();
        }
    }
}

From here on, only hasNext() remains. This method should also be clear now, as it can be implemented by inverting the while condition in next().

@Override
public boolean hasNext() {
    return stack.empty() && currentNode == null;
}

Advanced Features:

Most Java Collections keep track of a modification count or short, modCount. It stores the amount of times a Collection has been modified. This data can be used to detect when the underlying data structure has been illegally modified while iterating over it. Simply pass the modCount to the Iterator. Of course, you would have to implement that feature in your tree and increment the number each time it is modified.

public BSTIterator(BST<E, K> tree) {
    this.tree = tree;
    this.currentNode = tree.getRoot();
    this.expectedModCount = tree.modCount;
}

Then, implement fail-fast behaviour:

@Override
public E next() {
    if(expectedModCount != tree.modCount)
        throw new ConcurrentModificationException();
    // ...
}

Binary Search tree inorder iterator next method

1 Answers