A Binary Search Tree Implementation - Data Structures and Abstractions with Java - page 633

Question 4 When getEntry calls findEntry , it passes getRootNode() as the first argu-
ment. This argument's data type is BinaryNodeInterface<T> , which corresponds to the type
of the parameter rootNode . If you change rootNode 's type to BinaryNode<T> , what other
changes, if any, must you make?

25.10

The method contains . The method contains can simply call getEntry to see whether a given
entry is in the tree:

public boolean contains(T entry)
{

return getEntry(entry) != null ;
} // end contains

Traversing

25.11

SearchTreeInterface provides the method getInorderIterator , which returns an inorder itera-
tor. Since our class is a subclass of BinaryTree , it inherits getInorderIterator . For a binary
search tree, this iterator traverses the entries in ascending order, as defined by the entries' method
compareTo .

Question 5 Under what circumstance will a client of BinarySearchTree be able to call the
other methods in TreeIteratorInterface ? Under what circumstance will such a client be
unable to call these methods?

Adding an Entry

25.12

Adding entries to a binary search tree is an essential operation, since that is how we build one ini-
tially. So suppose that we have a binary search tree and we want to add a new entry to it. We cannot
add it just anywhere in the tree, because we must retain the relationships among the nodes. That is,
the tree must still be a binary search tree after the addition. Also, the method getEntry must be able
to locate the new entry. For example, if we want to add the entry Chad to the tree in Figure 25-4a, we
could not add the new node to Jared 's right subtree. Since Chad comes before Jared , Chad must be
in Jared 's left subtree. Since Brittany is the root of this left subtree, we compare Chad with Brittany
and find that Chad is larger. Thus, Chad belongs in Brittany 's right subtree. Continuing, we compare
Chad with Doug and find that Chad belongs in Doug 's left subtree. But this subtree is empty. That is,
Doug has no left child.
If we make Chad the left child of Doug , we will get the binary search tree in Figure 25-4b.
Now getEntry will be able to locate Chad by making the same comparisons we just described.
That is, getEntry will compare Chad with Jared , Brittany , and Doug before locating Chad . Notice
that the new node is a leaf.

VideoNote

Binary search tree additions
and removals

Note: Every addition to a binary search tree adds a new leaf to the tree.