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:

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.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.