The code for deleting a node from a binary search tree. Uses setData() of IntNode class.

The code is written by Scott Lembcke.



    // author: Scott Lembcke
    // Oct. 29th 2004
    public void delete(int data) {
	IntNode nodeParent = null;
	IntNode node = root;
	if (root == null) {
	    System.out.println("can't delete " + data + ": no such node");
	    return;
	}
	while(node.getData()!=data){
	    nodeParent = node;
	    if(data < node.getData()){
		node = node.getLeft();
	    } else {
		node = node.getRight();
	    }
	    if (node == null) {
		System.out.println("can't delete " + data + ": no such node");
		return;
	    }
	}
	if(node.getRight()!=null){
	    IntNode next = node.getRight();
	    IntNode nextParent = node;
	    boolean isLeft = false;
	    while(next.getLeft()!=null){
		nextParent = next;
		next = next.getLeft();
		isLeft = true;
	    }
	    node.setData(next.getData());
	    if(isLeft) nextParent.setLeft(next.getRight());
	    else nextParent.setRight(next.getRight());
	} else {
	    if(node!=root){
		if(node == nodeParent.getLeft()){
		    nodeParent.setLeft(node.getLeft());
		} else {
		    nodeParent.setRight(node.getLeft());
		}
	    }
	    else root = root.getLeft();

	}
    }

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.