Java List Iterator does not seem to be iterating properly

Question

I am writing a program that takes a binary tree and iterates through it in-order. To accomplish this, my iterator class traverses the tree and adds the elements to a list, and the list is then iterated through. In debugging my code, I have found out that the list contains 4 distinct elements just as it should, but in main when the list is printed, I get tinsel (the first element of the list) over and over in an infinite loop. Therefore, the iterator simply isn't iterating; it's getting stuck on the first element.

The iterator class:

import java.util.*;

@SuppressWarnings("rawtypes")
public class TreeIterator implements Iterator{

    BinaryTree BT;

    TreeIterator(BinaryTree BT){
        this.BT=BT;
        inOrder(BT.root);
    }

    private List<String> decorationList = new ArrayList<String>();

    private void inOrder(Node root){
        if(root==null) return;
        inOrder(root.left);
        String temp = root.decoration;
        decorationList.add(temp);
        inOrder(root.right);
    }

    public boolean hasNext() {
        return decorationList.iterator().hasNext();
    }

    public Object next() {
        return decorationList.iterator().next();
    }

    public void remove() {
        // this method is not implemented           
    }

}

The main function:

public class Main {
    public static void main(String[] args) {

        // build a test tree
        //
        //       star
        //      /    \
        // tinsel    red balls
        //      \
        //       lights
        BinaryTree BT = new BinaryTree();
        BT.root = new Node();
        BT.root.decoration = "star";
        BT.root.left = new Node();
        BT.root.left.decoration = "tinsel";
        BT.root.left.right = new Node();
        BT.root.left.right.decoration = "lights";
        BT.root.right = new Node();
        BT.root.right.decoration = "red balls";


        TreeIterator TI = BT.createIterator();
        while(TI.hasNext()){
            System.out.println(TI.next());
        }
    }
}

Let me know if I should add the Binary Tree implementation as well.

Answer 1

public Object next() {
    //                   vvvvvvvvvvv
    return decorationList.iterator().next();
}

You are creating a new Iterator each time you call these methods. That is why you are seeing the behavior that you are. Each time hasNext or next, is called, you make a new Iterator that starts at 0.

Instead, if you are writing an iterator that simply delegates to another, you should create it a single time in the constructor:

class IteratorDelegator<T> implements Iterator<T> {
    private final Iterator<? extends T> delegate;

    IteratorDelegator(Iterable<? extends T> iterable) {
        this.delegate = iterable.iterator();
    }

    @Override
    public T next() {
        return delegate.next();
    }

    ...
}

Also: in general we do not use raw types. If your BinaryTree is non-generic, you should implement Iterator<Object> instead of a raw type. Since decorationList is a List<String> it appears you should be implementing Iterator<String>.