public class LinkedBinaryTree implements BinaryTree {
  private Position root; // reference to the root
  private int size; // number of nodes
  public LinkedBinaryTree() {
    root = new BTNode(null,null,null,null);
    size = 1;
  }
  
  public int size() { return size; }
  public boolean isEmpty() { return (size==0); }
  public boolean isInternal(Position v) {
    return (((BTNode) v).getLeft()!=null && ((BTNode) v).getRight()!=null);
  }
  public boolean isExternal(Position v) {
    return (((BTNode) v).getLeft()==null && ((BTNode) v).getRight()==null);
  }
  public boolean isRoot(Position v) { return (v==root()); }

  public Position root() { return root; }
  public PositionIterator positions() {  
    Position[] positions = new Position[size()];
    inorderPositions(root(), positions, 0);
    return new ArrayPositionIterator(positions);
  }
  public Position leftChild(Position v) { return ((BTNode) v).getLeft(); }
  public Position rightChild(Position v) { return ((BTNode) v).getRight(); }
  public Position sibling(Position v) {
    Position p = parent(v);
    Position lc = leftChild(p);
    if (v == lc)
      return rightChild(p);
    else
      return lc;
  }
  public Position parent(Position v) { return ((BTNode) v).getParent(); }