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

Note the order of the tests. The test against null must be performed first; oth-
erwise, the access t.element would be illegal. The remaining tests are
arranged with the least likely case last. A recursive implementaion is possible,
but we use a loop instead; we use recursion in the insert and remove methods.
In Exercise 19.15 you are asked to write the searching algorithms recursively.

At first glance, statements such as t=t.left may seem to change the root
of the tree. That is not the case, however, because t is passed by value. In the
initial call, t is simply a copy of root . Although t changes, root does not. The
calls to findMin and findMax are even simpler because branching is uncondi-
tionally in one direction. These routines are shown in Figure 19.9. Note how
the case of an empty tree is handled.

Because of call by
value, the actual
argument ( root ) is
not changed.

The insert routine is shown in Figure 19.10. Here we use recursion to sim-
plify the code. A nonrecursive implementation is also possible; we apply this tech-
nique when we discuss red-black trees later in this chapter. The basic algorithm is
simple. If the tree is empty, we can create a one-node tree. The test is performed at
line 10, and the new node is created at line 11. Notice carefully that, as before,
local changes to t are lost. Thus we return the new root, t , at line 18.

For insert , we must
return the new tree
root and reconnect
the tree.

figure 19.9
The findMin and
findMax methods for
binary search trees

1 /**
2 * Internal method to find the smallest item in a subtree.
3 * @param t the node that roots the tree.
4 * @return node containing the smallest item.
5 */
6 protected BinaryNode<AnyType> findMin( BinaryNode<AnyType> t )
7 {
8 if( t != null )
9 while( t.left != null )
10 t = t.left;
11
12 return t;
13 }
14
15 /**
16 * Internal method to find the largest item in a subtree.
17 * @param t the node that roots the tree.
18 * @return node containing the largest item.
19 */
20 private BinaryNode<AnyType> findMax( BinaryNode<AnyType> t )
21 {
22 if( t != null )
23 while( t.right != null )
24 t = t.right;
25
26 return t;
27 }