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

// replace entry in currentNode with the entry in another node
// that has at most one child; that node can be deleted
// get node to remove (contains inorder predecessor; has at
// most one child) and its parent
pair = getNodeToRemove(currentNode);
BinaryNodeInterface<T> nodeToRemove = pair.getFirst();
parentNode = pair.getSecond();
// copy entry from nodeToRemove to currentNode
currentNode.setData(nodeToRemove.getData());
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
} // end if
// Case 2: currentNode has at most one child; delete it
removeNode(currentNode, parentNode);
} // end if
return result;
} // end remove

25.37

The private method findNode . To find the node that contains a match for a given entry, we use the
compareTo method within a loop to compare the given entry with the other entries in the tree. The
method returns a pair of references to the desired node and its parent as an instance of the class
NodePair . Thus, findNode has the following form:

private NodePair findNode(T entry)
{

NodePair result = new NodePair();
boolean found = false ;
. . .
if (found)
result = new NodePair(currentNode, parentNode);
// found entry is currentNode.getData()
return result;
} // end findNode
The details of the implementation of findNode are left as an exercise.

Question 10 Complete the implementation of the method findNode .

25.38

The private method getNodeToRemove . After remove locates the node that contains the entry to be
removed from the tree, it proceeds according the number of the node's children. If the node has two
children, remove must remove another node that has no more than one child. The private method
getNodeToRemove finds this node. In particular, the method implements the first step of the pseudo-
code given in Segment 25.25:

Find the rightmost node R in N's left subtree

Here, node N is currentNode and node R is rightChild .