BinarySearchTreeIterator.java

public class BinarySearchTreeIterator {
    private Stack<TreeNode> stack = null;

    public BinarySearchTreeIterator(TreeNode root) {
        this.stack = new Stack<TreeNode>();

        while (root != null) {
            this.stack.push(root);
            root = root.left;
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !this.stack.isEmpty();
    }

    /** @return the next smallest number */
    // essentially using a stack to implement in-order traversal
    public int next() {
        // caller should check using hasNext() else NoSuchElementException
        TreeNode t = this.stack.pop();

        if (t.right != null) {
            this.stack.push(t.right);

            TreeNode c = t.right.left;

            while (c != null) {
                this.stack.push(c);
                c = c.left;
            }
        }
        return t.val;
    }

}