public Node<T> getPredecessor(Node<T> node) {
    if (node.getLeft() != null) {
      node = node.getLeft();
      while (node.getRight() != null)
        node = node.getRight();
      return node;
    }
    Node<T> temp = node.getParent();
    while (temp != null && node == temp.getLeft()) {
      node = temp;
      temp = temp.getParent();
    }
    return temp;
  }