import java.util.*;

public class Tree
{
  private Node root;
  int numNodes;

  // Create a tree with just one node.
  public Tree(Item value)
  {
    root = new Node(value);
    numNodes = 1;
  }

  // A more useful constructor that will create a new tree with a 
  // given node as the root, along with 2 existing subtrees as its children.
  public Tree(Item value, Tree leftSubtree, Tree rightSubtree)
  {
    root = new Node(value);
    root.left = leftSubtree.root;
    root.right = rightSubtree.root;
    leftSubtree.root.parent = root;
    rightSubtree.root.parent = root;
    numNodes = leftSubtree.numNodes + rightSubtree.numNodes + 1;
  }

  public int size()
  {
    return numNodes;
  }

  // Let's use the preorder iterator to print the tree!
  public String toString()
  {
    String build = "";

    Iterator iter = preorderIterator(root);
    while(iter.hasNext())
	build += "\t" + ((Node) iter.next()).data + "\n";

    return build;
  }


  // Step 1:  Since the 3 traversals are so similar, factor out the code
  // all will need here - namely, the required functions for Iterator
  // and the 2 attributes "list" and "currentIndex".
  // You don't need a constructor.  The specific iterator classes
  // (preorder, inorder, postorder) will retain their constructors
  // because they need to call addNext(), which is different in each case.
  /* not implemented yet
  class GeneralIterator implements Iterator
  {

  }
    */

  // Step 2:  You need to take out code in PreorderIterator that has been 
  // moved into GeneralIterator.  The PreorderIterator class only
  // needs 2 methods:  the constructor, and addNext().
  class PreorderIterator implements Iterator
  {
    private ArrayList list;
    private int currentIndex;

    // Initialize our attributes to keep track of nodes in preorder,
    // and start the recursive process from the 'start' node.
    public PreorderIterator(Node start)
    {
      list = new ArrayList();
      addNext(start);
      currentIndex = 0;
    }

    // Recursive function to add nodes in a preorder manner
    public void addNext(Node n)
    {
      if (n == null)
	return;
      list.add(n);
      addNext(n.left);
      addNext(n.right);
    }

    public boolean hasNext()
    {
      return currentIndex < list.size();
    }

    public Object next()
    {
      return list.get(currentIndex++);
    }

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

  // Step 3:  Write classes for inorder and postorder traversals,
  // analogous to the above class for preorder.


  // Step 4:  The following functions allow us to create an iterator object
  // for a preorder traversal....
  // Write analogous functions for inorder and postorder.

  public Iterator preorderIterator(Node start)
  {
    return new PreorderIterator(start);
  }





  // Let's say that if they don't tell us where to start, the default
  // is to start traversing from the root.
  public Iterator preorderIterator()
  {
    return new PreorderIterator(root);
  }






}