import java.util.*;

public class PrefixTreePreorderIterator implements Iterator<String> {
	//Data
	LinkedList<String> list;
	Iterator<String> it;

	//Constructor
	public PrefixTreePreorderIterator(PrefixTree tree) {
		list = new LinkedList<String>();
		preorder(tree,"");
		reset();
	}
 
	//Private method
	private void preorder(PrefixTree tree,String s) {
		//Root visit
		s = s + tree.character();
		if(tree.endOfKey()) {
			if(s.length() == 0) list.addLast("");
			else list.addLast(s.substring(1));
		}
			
		//Subtrees visit
		PrefixTree[] child = tree.child();
		for(int i = 0; i < child.length; i++) {
			tree = child[i];
			if(tree != null)
   				preorder(tree,s);
   		}
	}

	//Iterator methods
	public boolean hasNext() { return it.hasNext(); }
	public String next() { return it.next(); }
	public void reset() { it = list.iterator(); }
	public void remove() { it.remove(); }
}