Implementation of in-order iterator over a binary search tree.

BST.java

package bst;

public interface BST<T extends Comparable<T>> {
    /**
     * Returns the value of the current node.
     */
    public T getValue();

    /**
     * Returns the left child node or null if there isn't one.
     */
    public BST<T> getLeftChild();

    /**
     * Returns the right child node or null if there isn't one.
     */
    public BST<T> getRightChild();
}

BSTUtils.java

package bst;

import com.google.common.base.Preconditions;
import com.google.common.collect.Iterators;

/**
 * Utility methods for {@link BST}.
 */
public abstract class BSTUtils {
    public static <T extends Comparable<T>> void printBST(BST<T> bst) {
        Preconditions.checkNotNull(bst, "Tree cannot be null");
        System.out.print(Iterators.toString(new InorderTraversal<T>(bst)));
    }
}

BSTUtilsTest.java

package bst;

import static org.junit.Assert.assertEquals;

import java.io.ByteArrayOutputStream;
import java.io.PrintStream;
import java.util.Arrays;

import org.junit.Test;

/**
 * {@link BSTUtils} unit tests.
 */
public class BSTUtilsTest {

    @Test
    public void printBST_shouldPrintToStdout() {
        ByteArrayOutputStream byteArray = new ByteArrayOutputStream();
        PrintStream testStream = new PrintStream(byteArray);
        PrintStream out = System.out;
        try {
            System.setOut(testStream);
            BSTUtils.printBST(InorderTraversalTest.TREE);
            testStream.flush();

            String actual = byteArray.toString();
            String expected = Arrays.asList(1, 3, 5, 6, 10, 12).toString();
            assertEquals(expected, actual);
        } finally {
            System.setOut(out);
        }
    }

    @Test(expected = NullPointerException.class)
    public void printBST_shouldFailOnNullArgument() {
        BSTUtils.printBST(null);
    }
}

InorderTraversal.java

package bst;

import java.util.Iterator;
import java.util.LinkedList;

import com.google.common.base.Preconditions;

/**
 * Iterates over {@link BST} nodes in order.
 */
public class InorderTraversal<T extends Comparable<T>> implements Iterator<T>, Iterable<T> {

    /**
     * Keeps the current node with all its parent nodes.
     */
    private final LinkedList<BST<T>> parents;

    /**
     * Constructs {@link BST} in-order iterator.
     * <p>
     * During construction thre's a walk to the leftmost node. The
     * walk may take O(n) time for unbalanced trees and O(logn) 
     * for balanced trees.
     * 
     * @param root
     *            The root of the tree.
     * @throws NullPointerException
     *             if root is <code>null</code>.
     */
    public InorderTraversal(BST<T> root) {
        Preconditions.checkNotNull(root, "Tree root cannot be null");
        this.parents = new LinkedList<BST<T>>();
        for (BST<T> current = root; current != null; current = current.getLeftChild()) {
            this.parents.push(current);
        }
    }

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

    /**
     * {@inheritDoc}
     * <p>
     * Amortized complexity of this method is O(1).
     */
    @Override
    public T next() {
        BST<T> current = parents.pop();
        for (BST<T> child = current.getRightChild(); child != null; child = child.getLeftChild()) {
            parents.push(child);
        }
        return current.getValue();
    }

    /**
     * {@inheritDoc}
     * <p>
     * Returns reference to itself.
     */
    @Override
    public Iterator<T> iterator() {
        return this;
    }

    /**
     * Remove method is not supported. Will throw
     * {@link UnsupportedOperationException}.
     */
    @Override
    public void remove() {
        throw new UnsupportedOperationException("remove is not supported");
    }

}

InorderTraversalTest.java

package bst;

import static org.junit.Assert.assertEquals;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

import org.junit.Test;

/**
 * {@link InorderTraversal} unit tests.
 */
public class InorderTraversalTest {

    /**
     * <pre>
     *      10
     *      / \
     *     5  12
     *    / \
     *   1   6
     *    \
     *     3
     * </pre>
     */
    static BST<Integer> TREE = bt(10,//
            bt(5, //
                    bt(1, null, bt(3, null, null)),//
                    bt(6, null, null)),//
            bt(12, null, null));

    @Test(expected = NullPointerException.class)
    public void ctorShouldFailOnNullArgument() {
        new InorderTraversal<Integer>((BST<Integer>) null);
    }

    @Test
    public void shouldTraverseInOrder() {
        List<Integer> expected = Arrays.asList(1, 3, 5, 6, 10, 12);
        List<Integer> actual = new ArrayList<Integer>();
        for (Integer value : new InorderTraversal<Integer>(TREE)) {
            actual.add(value);
        }
        assertEquals("Traversal of this tree", expected, actual);
    }

    @Test(expected = UnsupportedOperationException.class)
    public void shouldFailOnRemove() {
        new InorderTraversal<Integer>(TREE).remove();
    }

    @Test(expected = NoSuchElementException.class)
    public void shouldEndIterationWithNSEE() {
        Iterator<Integer> iter = new InorderTraversal<Integer>(TREE);
        while (iter.hasNext()) {
            iter.next();
        }

        // Should throw exception here.
        iter.next();
    }

    //
    // Private members
    //

    private static <T extends Comparable<T>> BST<T> bt(T value, BST<T> left, BST<T> right) {
        return new TestBST<T>(value, left, right);
    }

    //
    // Private classes
    //

    /**
     * Binary tree with arbitrary ordering.
     */
    private static class TestBST<T extends Comparable<T>> implements BST<T> {

        private final T value;
        private final BST<T> left;
        private final BST<T> right;

        public TestBST(T value, BST<T> left, BST<T> right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }

        @Override
        public T getValue() {
            return this.value;
        }

        @Override
        public BST<T> getLeftChild() {
            return this.left;
        }

        @Override
        public BST<T> getRightChild() {
            return this.right;
        }

        @Override
        public String toString() {
            return "TestBST [value=" + value + ", left=" + left + ", right=" + right + "]";
        }
    }

}