A Binary Search Tree Implementation - Data Structures and Abstractions with Java - page 649

In the second case, we delete the node itself. But if the node has two children, we delete another
node that has at most one child. That is, we transform Case 1 into Case 2.
The following pseudocode describes what remove must do:
Algorithm remove(entry)
result = null
currentNode = node that contains a match for entry
parentNode = currentNode 's paren t

if (currentNode != null ) // that is, if entry is found
{

result = currentNode 's data (the entry to be removed from the tree)

// Case 1
if (currentNode has two children )
{

// get node to remove and its parent
nodeToRemove = node containing entry 's inorder predecessor; it has at most one child
parentNode = nodeToRemove 's parent

Copy entry from nodeToRemove to currentNode
currentNode = nodeToRemove
// Assertion: currentNode is the node to be removed; it has at most one child
// Assertion: Case 1 has been transformed to Case 2

}

// Case 2: currentNode has at most one child
Delete currentNode from the tree

}

return result

25.36

The public method remove . We will implement the major steps of the previous algorithm as pri-
vate methods that remove can call. The private method findNode locates the node that contains a
match for the given entry. Since we need a reference to that node as well as one to its parent, we
make findNode return a pair of nodes. To that end, we design a private class NodePair that has con-
structors and the accessor methods getFirst and getSecond . NodePair will be an inner class of our
class BinarySearchTree .
The private method getNodeToRemove finds the node containing the inorder predecessor of the
the entry in a given node. Since we also need that node's parent, the method returns a pair of nodes
as an instance of the class NodePair .
Finally, the private method removeNode deletes a node that has at most one child. We give the
method references to the node and its parent, if any.
Using these private methods, we can implement remove , as follows:

public T remove(T entry)
{

T result = null ;
// locate node (and its parent) that contains a match for entry
NodePair pair = findNode(entry);
BinaryNodeInterface<T> currentNode = pair.getFirst();
BinaryNodeInterface<T> parentNode = pair.getSecond();
if (currentNode != null ) // entry is found
{

result = currentNode.getData(); // get entry to be removed
// Case 1: currentNode has two children
if (currentNode.hasLeftChild() && currentNode.hasRightChild())
{