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

or the named item is not present, then null is returned. Figure 19.7 shows the
private elementAt method that implements the elementAt logic.
The removeMin operation removes the minimum item from the tree; it
throws an exception if the tree is empty. The remove operation removes a
named item x from the tree; it throws an exception if warranted. The makeEmpty
and isEmpty methods are the usual fare.
As is typical of most data structures, the find operation is easier than
insert , and insert is easier than remove . Figure 19.8 illustrates the find routine.
So long as a null link has not been reached, we either have a match or need to
branch left or right. The code implements this algorithm quite succinctly.

1 /**
2 * Internal method to get element field.
3 * @param t the node.
4 * @return the element field or null if t is null.
5 */
6 private AnyType elementAt( BinaryNode<AnyType> t )
7 {
8 return t == null ? null : t.element;
9 }

figure 19.7
The elementAt method

1 /**
2 * Internal method to find an item in a subtree.
3 * @param x is item to search for.
4 * @param t the node that roots the tree.
5 * @return node containing the matched item.
6 */
7 private BinaryNode<AnyType> find( AnyType x, BinaryNode<AnyType> t )
8 {
9 while( t != null )
10 {
11 if( x.compareTo( t.element ) < 0 )
12 t = t.left;
13 else if( x.compareTo( t.element ) > 0 )
14 t = t.right;
15 else
16 return t; // Match
17 }
18
19 return null; // Not found
20 }

figure 19.8
The find operation for binary search trees