import java.util.List;
import java.util.LinkedList;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.Stack;

public class Tree<T> implements Iterable<T> {
    private TreeNode<T> root;
    
    /**
     * Constructor of a one node tree
     */
    public Tree(T rootData) {
        root = new TreeNode<T>(rootData);
    } // end constructor
    
    /**
     * Add a child to this tree
     * @param t is the subtree added
     */
    public void addChild(Tree<T> t) {
        root.children.add(t);
    }
    
    /**
     * Accessor for the root data
     * @return the root data of this tree
     */
    public T getData() {
        return root.data;
    }
    /**
     * Modifier of the root data
     * @param x is the new data
     */
    public void setData(T x) {
        root.data = x;
    }
    
    /**
     * Accessor for the children
     * @return the children of this tree
     */
    public List<Tree<T>> getChildren() {
        return root.children;
    }
    
    /**
     * Check for a leaf
     * @return true if this tree is a leaf; false otherwise
     */
    public boolean isLeaf() {
        return root.children.size() == 0;
    }
    
    
    /**
     * Returns an Iterator for this tree
     * @return a preorder Iterator for this tree
     */
    public Iterator<T> iterator() {
        return new TreePreorderIterator<T>(root);
    }
    
    /**
     * Returns a String of this tree's nodes in preorder
     * @return a String representation of this tree's nodes in preorder
     */
    
    public String toString() {
        String out = toPreorder(this);
        return "[" + out.substring(0,out.length()-2) + "]";
    } // end toString
     
    private String toPreorder(Tree<T> t) {
        String out = t.getData() + ", ";
        for( Tree<T> child : t.getChildren() ) {
            out += toPreorder(child);
        } // end for
        return out;
    } // end toPreorder
    
    /*This is an iterative version of toString()
    public String toString() {
        Stack<Tree<T>> s = new Stack<Tree<T>>();
        String out = "";
        s.push(this);
        while( !s.isEmpty() ) {
            Tree<T> next = s.pop();
            out += next.getData() + ", ";
            ListIterator<Tree<T>> itr = next.getChildren().listIterator(next.getChildren().size());
            while( itr.hasPrevious() ) s.push(itr.previous());
        }// end while
        return "[" + out.substring(0,out.length()-2) + "]";
    }//end toString
    */
    
    private static class TreeNode<T> {
        T data;
        List<Tree<T>> children;
        
        TreeNode(T x) {
            data = x;
            children = new LinkedList<Tree<T>>();
        } // end constructor
        
    } // end TreeNode
    
    // This is a preorder iterator for a tree
    private class TreePreorderIterator<T> implements Iterator<T> {
        Stack<TreeNode<T>> s;
        
        TreePreorderIterator(TreeNode<T> root) {
            s = new Stack<TreeNode<T>>();
            s.push(root);
        } // end constructor
        
        public boolean hasNext() {
            return !s.isEmpty();
        } // end hasNext
        
        public T next() {
            TreeNode<T> next = s.pop();
            ListIterator<Tree<T>> itr = next.children.listIterator(next.children.size());
            while( itr.hasPrevious() ) s.push((itr.previous()).root);
            return next.data;
        } // end next
        
        public void remove() {
            throw new UnsupportedOperationException();
        } // end remove
        
    } // end TreeIterator
    
} // end Tree