Java Reference
In-Depth Information
larger value in the tree. That replacement preserves the binary search tree property.
(Alternatively, you could use the largest element of the left subtreeȌsee Exercise
P16.16).
When removing a node with two children from a binary search tree, replace it with
the smallest node of the right subtree.
To locate the next larger value, go to the right subtree and find its smallest data value.
Keep following the left child links. Once you reach a node that has no left child, you
have found the node containing the smallest data value of the subtree. Now remove
that nodeȌit is easily removed because it has at most one child to the right. Then
store its data value in the original node that was slated for removal.
Figure 12
shows
the details. You will find the complete code at the end of this section.
Figure 11
Removing a Node with One Child
725
