Binary search trees - Data Structures and Problem Solving Using Java - page 696

figure 19.11
The removeMin
method for the
BinarySearchTree
class

1 /**
2 * Internal method to remove minimum item from a subtree.
3 * @param t the node that roots the tree.
4 * @return the new root.
5 * @throws ItemNotFoundException if t is empty.
6 */
7 protected BinaryNode<AnyType> removeMin( BinaryNode<AnyType> t )
8 {
9 if( t == null )
10 throw new ItemNotFoundException( );
11 else if( t.left != null )
12 {
13 t.left = removeMin( t.left );
14 return t;
15 }
16 else
17 return t.right;
18 }

The method that has p as a parameter (in other words, the method that called
the current method) changes p.left to the new t . Thus the parent's left link
references t , and the tree is connected. All in all, it is a nifty maneuver—we
have maintained the parent in the recursion stack rather than explicitly kept
track of it in an iterative loop.
Having used this trick for the simple case, we can then adapt it for the
general remove routine shown in Figure 19.12. If the tree is empty, the remove
is unsuccessful and we can throw an exception at line 11. If we do not have a
match, we can recursively call remove for either the left or right subtree, as
appropriate. Otherwise, we reach line 16, indicating that we have found the
node that needs to be removed.

Recall (as illustrated in Figure 19.4) that, if there are two children, we
replace the node with the minimum element in the right subtree and then
remove the right subtree's minimum (coded at lines 18-19). Otherwise, we
have either one or zero children. If there is a left child, we set t equal to its left
child, as we would do in removeMax . Otherwise, we know that there is no left
child and that we can set t equal to its right child. This procedure is succinctly
coded in line 22, which also covers the leaf case.
Two points need to be made about this implementation. First, during the
basic insert , find , or remove operation, we use two three-way comparisons per
node accessed to distinguish among the cases < , = , and > . Obviously we can
compute x.compareTo(t.element) once per loop iteration, and reduce the cost
to one three-way comparison per node. Actually, however, we can get by with

The remove routine
involves tricky cod-
ing but is not too
bad if recursion is
used. The case for
one child, root with
one child, and zero
children are all han-
dled together at
line 22 .