/**
  * An implementation of the BinaryTree interface by means of a linked structure.
  */
public class LinkedBinaryTree implements BinaryTree {
  protected Position root;	// reference to the root
  protected int size;		// number of nodes
  /**  Creates an empty binary tree. */
  public LinkedBinaryTree() { 		    
    root = null;  // start with an empty tree
    size = 0;
  }
  // BinaryTree interface methods
  /** Returns the number of nodes in the tree. */
  public int size() {
    return size; 
  } 
  /** Returns whether the tree is empty. */
  public boolean isEmpty() {
    return (size==0); 
  } 
  /** Returns whether a node is internal. */
  public boolean isInternal(Position v) throws InvalidPositionException {
    checkPosition(v);	// auxiliary method
    return (hasLeft(v) || hasRight(v));
  }
  /** Returns whether a node is external. */
  public boolean isExternal(Position v) throws InvalidPositionException {
    return !isInternal(v);
  }
  /** Returns whether a node is the root. */
  public boolean isRoot(Position v) throws InvalidPositionException { 
    checkPosition(v);
    return (v == root()); 
  }
  /** Returns whether a node has a left child. */
  public boolean hasLeft(Position v) throws InvalidPositionException { 
    BTPosition vv = checkPosition(v);
    return (vv.getLeft() != null);
  }
  /** Returns whether a node has a right child. */
  public boolean hasRight(Position v) throws InvalidPositionException { 
    BTPosition vv = checkPosition(v);
    return (vv.getRight() != null);
  }