// Binary search tree of Strings
//
// with an iterator

import java.util.*;


class BST2 {

    private class Node {

	public String data;
	public Node left;
	public Node right;
	public Node parent;

	Node( String data, Node parent ) {
	    this.data = data;
	    this.left = null;
	    this.right = null;
	    this.parent = parent;
	}
    }

    Node root;

    BST2() {
	root = null;
    }

    // ---- INSERT A STRING ----

    public void insert( String str ) {
	if (root == null)
	    root = new Node( str, null );
	else
	    insert( str, root );
    }

    private void insert( String str, Node n ) {
	if (str.compareTo( n.data ) < 0)
	    if (n.left == null)
		n.left = new Node( str, n );
	    else
		insert( str, n.left );
	else
	    if (n.right == null)
		n.right = new Node( str, n );
	    else
		insert( str, n.right );
    }

    // ---- ITERATOR ----

    private class BSTOrderedIterator implements Iterator {

	Node nextNode;

	private BSTOrderedIterator() {

	    if (root == null)
		nextNode = null;
	    else { // Start at the leftmost node on the tree
		nextNode = root;
		while (nextNode.left != null)
		    nextNode = nextNode.left;
	    }
	}

	public boolean hasNext() {
	    return (nextNode != null);
	}
	    
	public Object next() {

	    if (nextNode == null)
		throw new NoSuchElementException();

	    String str = nextNode.data;

	    if (nextNode.right != null) {  // Find leftmost node in right subtree
		
		nextNode = nextNode.right;
		while (nextNode.left != null)
		    nextNode = nextNode.left;

	    } else { // Find nearest ancestor (above) to the right

		while (nextNode.parent != null && nextNode.parent.right == nextNode)
		    nextNode = nextNode.parent;

		nextNode = nextNode.parent;
	    }

	    return str;
	}

	public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    BSTOrderedIterator createOrderedIterator() {
	return new BSTOrderedIterator();
    }

    // ---- TESTING CODE ----

    public static void main( String [] args ) {

	BST2 bst = new BST2();

	for (int i=0; i<args.length; i++)
	    bst.insert( args[i] );

	Iterator iter = bst.createOrderedIterator();

	while (iter.hasNext())
	    System.out.println( (String) iter.next() );
    }
}