Tuesday, November 15, 2011

Java iterator for a binary search tree

Java has a commonly used Iterator interface.
It is no-where as cool as implicit python iterators, but it may be useful every now and then.
It is usually used like this:
Iterator e = container.iterator();  
while (e.hasNext())  
{  
    System.out.println(e.next());
}  
How do we implement a binary search tree iterator?
Look at the code here for binary search tree iterative traversal.
A simplest solution would be to "print" a tree into a storage array and then allow the iterator to operate on this array.
Alternatively (as shown here), we can use the iterative method developed earlier to maintain iterator state.
A basic idea for this iterator is saving a pointer (I call it a cursor) to a most recently found element.
Since the iterator has to access a lot of the tree's internals, I like to declare it as a private class inside my binary search tree implementation.
Such an approach ensures that variables such as tree.root are not seen from the outside.
Here is a simple implementation of an iterator that allows in-order traversal:
private class BSTIterator implements Iterator
{
    Node root, cursor;
    Stack  iteratorStack;

    public BSTIterator (BSTNode root)
    {
        this.root = root;
        this.cursor = root;
        this.iteratorStack = new Stack ();
    }

    public boolean hasNext()
    {
        return (!iteratorStack.empty() || cursor != null);
    }

    public Comparable next()
    {
        Comparable nextNodeValue;
        while (cursor != null)
        {
            iteratorStack.push(cursor);
            cursor = cursor.leftChild;
        }
        cursor = iteratorStack.pop();
        nextNodeValue = cursor.key;
        cursor = cursor.rightChild;
        return nextNodeValue;
    }
}
The things to notice here are that we just broke up the iterative method into separate chunks inside this class.
All of our local variables moved to class globals.
The while condition became the hasNext() boolean.
The body of the iterative method was modified for next().
As a result, we get nice, clean, multipurpose code.

1 comment:

  1. Hey man, Java does not allow private class to be declared.

    ReplyDelete