Linked Data Structures - Java - page 829

EXAMPLE: (continued)
then item is in the left subtree (if it is anywhere in the tree), and if
item > subTreeRoot.data
then item is in the right subtree (if it is anywhere in the tree).
The method with the following heading uses techniques very much like those used in
isInSubtree :
private IntTreeNode insertInSubtree(
int item, IntTreeNode subTreeRoot)
However, there is something new here. We want the method insertInSubtree to insert a
new node with the data item into the tree with root node subTreeRoot . But in this case we
want to deal with subTreeRoot as a variable and not use it only as the value of the variable
subTreeRoot . For example, if subTreeRoot contains null , then we want to change the value
of subTreeRoot to a reference to a new node containing item . However, Java parameters can-
not change the value of a variable given as an argument. (Review the discussion of parameters
in Chapter 5 if this sounds unfamiliar.) So, we must do something a little different. To change
the value of the variable subTreeRoot , we return a reference to what we want the new value to
be, and we invoke the method subTreeRoot as follows:
subTreeRoot = insertInSubtree(item, subTreeRoot);
That explains why the method insertInSubtree returns a reference to a tree node, but we
still have to explain why we know it returns a reference to the desired (modified) subtree.
Note that the method insertInSubtree searches the tree just as the method isInSubtree
does, but it does not stop if it finds item ; instead, it searches until it reaches a leaf node—that is,
a node containing null . This null is where the item belongs in the tree, so it replaces null with
a new subtree containing a single node that contains item . You may need to think about the
method insertInSubtree a bit to see that it works correctly; allow yourself some time to study
the method insertInSubtree and be sure you are convinced that after the addition, like so,
subTreeRoot = insertInSubtree(item, subTreeRoot);
the tree with root node subTreeRoot still satisfies the Binary Search Tree Storage Rule.
The rest of the definition of the class IntTree is routine.