public BinarySearchTreeNode<T> getPredecessorNode() {
    /**
     * Case 1: Node has left child
     * If a node X has a left child, then node X's predecessor node is the
     * maximum value of the left child node (i.e., you perform the maximum
     * operation on that left child). The result of performing the maximum
     * operation on the left child could either be the left child itself
     * (if the left child has no right child) or you trace all the way down
     * the right until you reach the leaf node (which would be the maximum).
     */
    if (leftChild != null) {
      return leftChild.getMaximumNode();
    }

    /**
     * Case 2: Node has no left child
     * If a node X has no left child, then node X's predecessor is found by
     * tracing back up the tree until you find a node that is a right child.
     * X's predecessor is the parent of that right child. In other words,
     * if node X has no left child, you trace back up the tree until you have
     * the first opportunity to turn left and X's successor is the first node
     * after turning left as you traverse back up the graph. It is important
     * that X might be the first node that is a right child.
     */
    // Seed the operation by starting with the current node as a parent.
    BinarySearchTreeNode<T> parentNode = this;
    while (parentNode != null) {
      if (parentNode.parent != null &&
          parentNode.parent.rightChild == parentNode) {
        return parentNode.parent;
      }

      // Walk up the tree.
      parentNode = parentNode.parent;
    }
    return null;
  }