/** Adds a root node to an empty tree */
  public Position addRoot(Object e) throws NonEmptyTreeException {
    if(!isEmpty())
      throw new NonEmptyTreeException("Tree already has a root");
    size = 1;
    root = createNode(e,null,null,null);
    return root;
  }
  /** Attaches two trees to be subtrees of an external node. */
  public void attach(Position v, BinaryTree T1, BinaryTree T2) 
    throws InvalidPositionException {
    if (isInternal(v))
      throw new InvalidPositionException("Cannot attach from internal node");
    BTPosition vv = (BTPosition)v;
    if (!T1.isEmpty()) {
      vv.setLeft((BTPosition) T1.root());
      ((BTPosition)T1.root()).setParent(vv);  // T1 should be invalidated
    }
    if (!T2.isEmpty()) {
      vv.setRight((BTPosition) T2.root());
      ((BTPosition)T2.root()).setParent(vv);  // T2 should be invalidated
    }
  }
  /** If v is a good binary tree node, cast to BTPosition, else throw exception */
  protected BTPosition checkPosition(Position v) 
    throws InvalidPositionException {
    if (v == null || !(v instanceof BTPosition))
      throw new InvalidPositionException("The position is invalid");
    return (BTPosition) v;
  }
  /** Creates a new binary tree node */
  protected BTPosition createNode(Object element, BTPosition parent, 
				  BTPosition left, BTPosition right) {
    return new BTNode(element,parent,left,right); }
  /** Creates a list storing the the nodes in the subtree of a node,
    * ordered according to the inorder traversal of the subtree. */
  protected void inorderPositions(Position v, List pos) 
    throws InvalidPositionException {
    if (hasLeft(v))
      inorderPositions(left(v), pos);  // recurse on left child
    pos.insertLast(v);
    if (hasRight(v))
      inorderPositions(right(v), pos); // recurse on right child
  }