// returns true if all nodes in this tree have correct parent links;
  // otherwise returns false;
  // each node should be the parent of its left and right children;
  // the root node's parent should be null
  private boolean verifyParentLinks()
  {
    return verifyParentLinksHelper(root, null); 1
  }

  private boolean verifyParentLinksHelper(TreeNode t, TreeNode parent)
  {
    return (t == null ||
                (t.getParent() == parent && 
                     verifyParentLinksHelper(t.getLeft(), t) &&
                     verifyParentLinksHelper(t.getRight(), t)));
  }

1. This method needs a helper method, because the root of the tree is different from the other nodes: its parent is null.

  // returns the node which is the successor of t in this tree;
  // returns null if t contains the maximum value in this tree;
  // the method runs in time O(h), where h is the height
  // of the tree rooted at t 1
  // precondition:  t is a node in this tree;
  //                all nodes in this tree have correct parent links
  private TreeNode successor(TreeNode t) 2
  {
    if (t == null)
      return null; 3

    TreeNode rightChild = t.getRight();

    if (rightChild != null)
      return minNode(rightChild);

    TreeNode parent = t.getParent();
    while (parent != null && parent.getRight() == t) 4
    {
      t = parent;
      parent = t.getParent();
    }

    return parent;
  }

1. It was supposed to say "rooted at root".  To find the successor, we may need to go from t all the way up to root.
   
   
2. You have to consider several situations in this algorithm.  The pictures of trees in the exam booklet should help you figure it out.
   
   
3. This check is redundant since the precondition states
   that t is a node in this tree.
   
   
4. Or:

       while (parent != null && ((Comparable)parent.getValue()).compareTo(t.getValue()) < 0)