// no parent links, so need to use a stack, taking O(height) space

	private LinkedList<TreeNode> stack; 
		// nodes who've been L but not data and R

	public TreeIterator() {
	     stack = new LinkedList<TreeNode>();
	     if (root != null) addAllLeft(root);
	}

	public boolean hasNext() {
	    return !stack.isEmpty();
	}

	public Comparable next() {
	    if (!hasNext()) throw new NoSuchElementException();
	    TreeNode node = (TreeNode)stack.removeFirst();
	    if (node.right != null) addAllLeft(node.right); 
	// successor is either RL* or a bigger parent 
	    return node.data;
	}

	// precondition root is not null
	private void addAllLeft(TreeNode node) {
	    do {
		stack.addFirst(node);
	        node = node.left;
	    } while(node != null);	     
	}
    }    
}


// parent links, so only O(1) space needed

	private TreeNode next;

	public TreeIterator() {
	    if (root!=null) next=findMin(root);
	}

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

	public Comparable next() {
	    if (!hasNext()) throw new NoSuchElementException();
	    Comparable ret=next.data;
	    if (next.right != null) next=findMin(next.right);
	    else {
		while(next.parent!=null && next==next.parent.right)
                  next=next.parent;
		next=next.parent;
	    } 
	    return ret;
	}

	private TreeNode findMin(TreeNode node) {
	    while(node.left != null) node=node.left;
            return node;
	}
    }    
}