Deleting a node involves two steps:

1. Locating the node to be deleted.
2. Eliminating that node from the data structure.

After locating the node to be deleted, we must determine the nature of that node.

1. If it is a leaf, make the parent node point to null.
2. If it has one child on the right, make the parent node point to the right child.
3. If it has one child on the left, make the parent node point to the left child.
4. If it has two children, the problem becomes much harder to solve.

Diagram 30-1

The leaf node containing the value 43 will be easy to delete. The parent node of the node containing 43 will change its right pointer to null.

Deleting a node with one child on the right, like the node with value 10, will involve rerouting the node from its parent to its single right child.

But deleting the node with value 29, a node with two children, involves breaking off subtrees and reattaching them at the proper location.

The code to implement deletion from a binary tree is given in Handout AB30.1, Deletion from a Binary Tree. The recursive deleteHelper method that locates the node to be deleted is given below:

private TreeNode deleteHelper( TreeNode node, Comparable target )
{
  if ( node == null )
  {
    throw new NoSuchElementException();
  }
  else if ( target.equals( node.getValue() ) )
  {
    return deleteTargetNode( node );
  }
  else if ( target.compareTo( node.getValue() ) < 0 )
  {
    node.setLeft( deleteHelper( node.getLeft(), target ) );
    return node;
  }
  else  //target.compareTo( root.getValue() ) > 0
  {
    node.setRight(deleteHelper( node.getRight(), target ) );
    return node;
  }
}

The delete method passes the root of the tree (myRoot) and the target item to be located to the deleteHelper method. The deleteHelper method receives a TreeNode reference alias (node). The deleteHelper method has 4 scenarios:

1. node == null, the value does not exist in the tree, throw a NoSuchElementException.
2. We found the correct node (target.equals(node.getValue())), call deleteTargetNode and pass it node.
3. Did not find the node yet, recursively call deleteHelper and pass it the internal reference to the left child.
4. Recursively call deleteHelper and pass it the internal reference to the right child.