Wednesday, April 08, 2009

a beautiful implementation of iterator for binary search tree

This is a beautiful implementation of an iterator for a Binary Search Tree.

private class treeIterator implements Iterator {
private Stack pose; // Java stack

//Constructor
private treeIterator() {
// Declare the stack in the constructor for each copy of our iterator
pose = new Stack();
slideLeft(root);
}

/**
* Traverse the Binary Search tree and place all the elements in the right order in the tree
* @param node
*/
private void slideLeft(Node node) {
while (node != null) {
pose.push(node);
node = node.left;
}
}

/**
* Returns true if the stack has elements and False if it is empty
*/
public boolean hasNext() {
return !pose.isEmpty();
}

/**
* Here we use peep to get the element from the stack and pop to remove it
* and in this way we go through the whole BST IF we need it !!!
*/
public E next() {
if (pose.isEmpty())
throw new NoSuchElementException(
"No more elements left in the iterator.");
E element = pose.peek().element;
slideLeft(pose.pop().right);
return element;
}

public void remove() {
throw new UnsupportedOperationException("n");
}
}//end of Iterator

No comments: