Deletion of a node in a binary search tree

Question

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;
}

Answer 1

Inefficient search step during delete

The search step here is inefficient:

private Node delete(int val, Node node) {
    if(search(val) == null) { //search to see if the value exists in the BST
        return null;
    }
    else{
        // ...
    }

The problem is that when the target value exists in the tree, it will be re-searched in every step as you descend in the tree until the node. It would be better to rewrite without this search step.

Complicated condition

The second condition here is a bit long and as such error-prone:

//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);
}

It will be simpler if you reorder these conditions:

//node is a leaf
if(node.left == null && node.right == null) {
    deleteLeafNode(node);
}
//node has 2 children
else if(node.left != null && node.right != null) {
    deleteTwoChildNode(node);
}
//node has one child
else {
    deleteSingleChildNode(node);
}

Overcomplicated deleteSingleChildNode

When the node to delete has only one child, it doesn't really matter if the child is in left or right position. You can simply pick that child, update its parent, and update the link in the parent of the deleted node, that's it.