This is a method that deletes a node. If the node has two leaves, it gets replaced by its predecessor in in-order traversal. Let N1 be the node we are deleting, N2 - its predecessor (i.e. the rightmost node of the left subtree of N1) if it exists. Note that N2 doesn't have to be a leaf, but it doesn't have the right child.

The algorithm:

If N1 is a leaf, set its parent's reference to it to null.
If N1 has just one child, set its parent's reference to it to the address of its child.
If N1 has two children, then it must have a predecessor N2 (see above). To delete N1, replace its data by that of N2. Then replace the reference to N2 from its parent by the address of N2's left child (which may or may not be null).

Note that while deleting a root follows the same pattern, we need to replace the data in the root. Our solution is to handle this case explicitly.

Here is the code that was written in class (with the corrections made in the lab):


    public void delete(int x) {
	IntNode n1 = search(x);
	if (n1 == null) {
	    System.out.println(x + " is not in the tree");
	}
	//n1 has two children:
	else if (n1.getLeft() != null && n1.getRight() != null) {
	    IntNode n2 = n1.getLeft();
	    IntNode n3 = n1;
	    while (n2.getRight() != null) {
		n3 = n2;
		n2 = n2.getRight();
	    }
	    n1.setData(n2.getData());
	    if (n3.getRight() == n2) {
		n3.setRight(n2.getLeft());
	    } else {
		n3.setLeft(n2.getLeft());
	    }
	}
	// n1 is the root:
	else if (n1 == root) {
	    if (n1.getRight() != null) {
		root = n1.getRight();
	    } else {
		root = n1.getLeft();
	    }
	} else {
	    // need to find n1's parent
	    IntNode parent = root;
	    while (parent.getLeft() != n1 && parent.getRight() != n1) {
		if (x < parent.getData()) {
		    parent = parent.getLeft();
		} else {
		    parent = parent.getRight();
		}
	    }
	    if (n1.getLeft() != null) {
		if (parent.getLeft() == n1) {
		    parent.setLeft(n1.getLeft());
		} else {
		    parent.setRight(n1.getLeft());
		}
	    } else {
		if (parent.getLeft() == n1) {
		    parent.setLeft(n1.getRight());
		} else {
		    parent.setRight(n1.getRight());
		}
	    }
	}
    }

This is an example from CSci 2101 course.