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

The details of this step are described by the following pseudocode:
// find the inorder predecessor by searching the left subtree; it will be the largest
// entry in the subtree, occurring in the node as far right as possible
leftSubtreeRoot = left child of currentNode
rightChild = leftSubtreeRoot
priorNode = currentNode

while (rightChild has a right child )
{

priorNode = rightChild
rightChild = right child of rightChild

}
// Assertion: rightChild is the node to be removed and has no more than one child

The following Java code implements getNodeToRemove :
private NodePair getNodeToRemove(BinaryNodeInterface<T> currentNode)
{

// find node with largest entry in left subtree by
// moving as far right in the subtree as possible
BinaryNodeInterface<T> leftSubtreeRoot = currentNode.getLeftChild();
BinaryNodeInterface<T> rightChild = leftSubtreeRoot;
BinaryNodeInterface<T> priorNode = currentNode;
while (rightChild.hasRightChild())
{

priorNode = rightChild;
rightChild = rightChild.getRightChild();
} // end while
// rightChild contains the inorder predecessor and is the node to
// remove; priorNode is its parent
return new NodePair(rightChild, priorNode);
} // end getNodeToRemove

25.39

The private method removeNode . Our last method assumes that the node to remove—call it
nodeToRemove —has at most one child. If nodeToRemove is not the root, parentNode is its parent.
The method begins by setting childNode to the child, if any, of nodeToRemove . If nodeToRemove
is a leaf, childNode is set to null . Then the method removes nodeToRemove , accounting for the case
when the node is the root as follows:
if (nodeToRemove is the root of the tree )
Set the root of the tree to childNode
else
Link parentNode to childNode , thereby deleting nodeToRemove

If we set the root of the tree to childNode , realize that we will correctly set the root to null if
nodeToRemove is a leaf.
The implementation of removeNode follows:

private void removeNode(BinaryNodeInterface<T> nodeToRemove,
BinaryNodeInterface<T> parentNode)

{

BinaryNodeInterface<T> childNode;
if (nodeToRemove.hasLeftChild())
childNode = nodeToRemove.getLeftChild();
else
childNode = nodeToRemove.getRightChild();