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

If the tree is not already empty, we have three possibilities. First, if the
item to be inserted is smaller than the item in node t , we call insert recur-
sively on the left subtree. Second, if the item is larger than the item in node t ,
we call insert recursively on the right subtree (these two cases are coded at
lines 12 to 15). Third, if the item to insert matches the item in t , we throw an
exception.
The remaining routines concern deletion. As described earlier, the
removeMin operation is simple because the minimum node has no left child.
Thus the removed node merely needs to be bypassed, which appears to
require us to keep track of the parent of the current node as we descend the
tree. But, again, we can avoid the explicit use of a parent link by using recur-
sion. The code is shown in Figure 19.11.

If the tree t is empty, removeMin fails. Otherwise, if t has a left child, we
recursively remove the minimum item in the left subtree via the recursive call
at line 13. If we reach line 17, we know that we are currently at the minimum
node, and thus t is the root of a subtree that has no left child. If we set t to
t.right , t is now the root of a subtree that is missing its former minimum ele-
ment. As before, we return the root of the resulting subtree. That is what we
do at line 17. But doesn't that disconnect the tree? The answer again is no. If t
was root , the new t is returned and assigned to root in the public method. If t
was not root , it is p.left , where p is t 's parent at the time of the recursive call.

The root of the new
subtree must be
returned in the
remove routines. In
effect we maintain
the parent in the
recursion stack.

1 /**
2 * Internal method to insert into a subtree.
3 * @param x the item to insert.
4 * @param t the node that roots the tree.
5 * @return the new root.
6 * @throws DuplicateItemException if x is already present.
7 */
8 protected BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
9 {
10 if( t == null )
11 t = new BinaryNode<AnyType>( x );
12 else if( x.compareTo( t.element ) < 0 )
13 t.left = insert( x, t.left );
14 else if( x.compareTo( t.element ) > 0 )
15 t.right = insert( x, t.right );
16 else
17 throw new DuplicateItemException( x.toString( ) ); // Duplicate
18 return t;
19 }

figure 19.10
The recursive insert for the BinarySearchTree class