I am looking to see if my implementation of the removal/deletion method in a binary search tree is sufficient, readable, and runs in \$O(\log n)\$ time. It's been awhile since I've written a data structure and wanted to see if I still had it.

The basic structure of my BST is a Node with 3 pointers. A pointer to its parent, a pointer to its left child, and a pointer to its right child.

There are 3 basic cases in removing a node from a BST

**Case 1:** Leaf node, just detach the node from the BST and return it

**Case 2:** One Child, if the child is a left child replace the node with its predecessor. If it is a right child, replace it with its successor.

**Case 3:** 2 children. We can either replace the node with its successor or predecessor. In my implementation I just chose to replace it with its predecessor.

Code: 

 /**
 * the public method that is accessible for deletion
 * @param val the value to be removed from the BST
 * @return the node with the specified value
 */
 public Node delete(int val) {
 return delete(val, root);
 }
 
 /**
 * private helper method for the public delete method.
 * @param val the value to be searched and removed
 * @param node the current node we are checking to see if it has the same value as the val param
 * @return the node that we are removing
 */
 private Node delete(int val, Node node) {
 if(search(val) == null) { //search to see if the value exists in the BST
 return null;
 }
 else{
 if(val < node.val){
 return delete(val, node.left);
 }
 else if(val > node.val){
 return delete(val, node.right);
 }
 else{
 //node is a leaf
 if(node.left == null && node.right == null) {
 deleteLeafNode(node);
 }
 //node has one child
 else if((node.left != null && node.right == null) || (node.left == null && node.right != null)){
 deleteSingleChildNode(node);
 }
 //node has 2 children
 else {
 deleteTwoChildNode(node);
 }
 return node;
 }
 }
 }
 
 /**
 * detaches a node from its parent
 * @param node the node to be detached from its parent
 */
 private void deleteLeafNode(Node node){
 detach(node);
 }
 
 /**
 * removes a node from the BST that has a single child. The node might have a right child or left child
 * if it has a left child it is replaced by its predecessor. If the predecessor has a child it will be relinked 
 * if it has a right child it is replaced bu its successor. If the successor has a child it will be relinked
 * @param node the node to be deleted
 */
 private void deleteSingleChildNode(Node node){
 if(node.left != null){
 Node predecessor = getPredecessor(node);
 if(predecessor.left != null){
 //relink the predecessor's child to its parent
 predecessor.parent.right = predecessor.left;
 predecessor.left.parent = predecessor.parent;
 //replace the current node with the predecessor
 node.left.parent = predecessor;
 if(predecessor != node.left) { //will cause the predecessor to point to itself. Infinite loop
 predecessor.left = node.left;
 }
 predecessor.parent = node.parent;
 }
 else {
 //just
 node.left.parent = predecessor;
 predecessor.parent.right = null;
 if(node.left != predecessor){ //will cause the predecessor to point to itself. Infinite loop
 predecessor.left = node.left;
 }
 predecessor.parent = node.parent;
 }
 detach(node, predecessor);
 }
 //node has a right branch
 else{
 Node successor = getSuccessor(node);
 if(successor.right != null){
 //relink the predecessor's child to its parent
 successor.parent.left = successor.right;
 successor.right.parent = successor.parent;
 //replace the current node with the successor
 node.right.parent = successor;
 if(node.right != successor) { //will cause the successor to point to itself. Infinite loop
 successor.right = node.right;
 }
 successor.parent = node.parent;
 }
 else {
 node.right.parent = successor;
 successor.parent.left = null;
 if(node.right != successor) { //will cause the successor to point to itself. Infinite loop
 successor.right = node.right;
 }
 successor.parent = node.parent;
 }
 detach(node, successor);
 }
 }
 
 /**
 * removes a node from the BST that has two children.
 * we replace the node with its predecessor. If the predecessor has a child it will be relinked
 * @param node the node to be deleted
 */
 private void deleteTwoChildNode(Node node){
 //we can choose to either replace with the successor or predecessor. Just go with predecessor
 Node predecessor = getPredecessor(node);
 if(predecessor.left != null){
 //relink the predecessor's child to its parent
 predecessor.parent.right = predecessor.left;
 predecessor.left.parent = predecessor.parent;
 //replace the current node with the predecessor
 node.left.parent = predecessor;
 if(node.left != predecessor) {
 predecessor.left = node.left;
 }
 predecessor.parent = node.parent;
 }
 else {
 node.left.parent = predecessor;
 predecessor.parent.right = null;
 if(predecessor != node.left) { //will cause the predecessor to point to itself. Infinite loop
 predecessor.left = node.left;
 }
 predecessor.parent = node.parent;
 }
 if(predecessor != node.left) { //will cause the predecessor to point to itself. Infinite loop
 predecessor.left = node.left;
 }
 predecessor.right = node.right;
 node.left.parent = predecessor;
 node.right.parent = predecessor;
 detach(node, predecessor);
 }
 
 /**
 * detached a node from its parent
 * @param node the node to be detached
 */
 private void detach(Node node){
 if(node != root) {
 if (node.parent.left == node) {
 node.parent.left = null;
 } else {
 node.parent.right = null;
 }
 }
 else {
 root = null;
 }
 }
 
 /**
 * detaches a node from its parent. Replaces the parents child with the replacement node
 * @param current the current node to be removed
 * @param replacement the replacement node to replace the current node
 */
 private void detach(Node current, Node replacement){
 if(current != root) {
 if (current.parent.left == current) {
 current.parent.left = replacement;
 } else {
 current.parent.right = replacement;
 }
 }
 else{
 root = replacement;
 root.parent = null;
 }
 }
 
 /**
 * returns the successor of a node
 * @param node the node we want to produce a successor of
 * @return the successor
 */
 private Node getSuccessor(Node node){
 Node successor = node;
 if(successor.right != null){
 successor = successor.right;
 while(successor.left != null){
 successor = successor.left;
 }
 }
 else{
 successor = null;
 }
 return successor;
 }
 
 /**
 * returns a predecessor of a node
 * @param node the node we want to produce a predecessor of
 * @return the predecessor
 */
 private Node getPredecessor(Node node){
 Node predecessor = node;
 if(predecessor.left != null){
 predecessor = predecessor.left;
 while(predecessor.right != null){
 predecessor = predecessor.right;
 }
 }
 else {
 predecessor = null;
 }
 return predecessor;
 }