Introduction to Binary Trees - Advanced Topics in Java: Core Concepts in Data Structures - page 230

Searching such a tree is reduced to a sequential search of a linked list. This kind of tree is called a degenerate
tree. Certain orders of the words will give some very unbalanced trees. As an exercise, draw the trees obtained for the
following orders of the words:

• vim tee ria ode mac lea era

• era vim lea tee mac ria ode

• vim era lea tee ria mac ode

• lea mac vim tee era ria ode

8.7 Building a Binary Search Tree
We now write a function to find or insert an item in a binary search tree. Assuming the previous definitions of
TreeNode and BinaryTree , we write the function findOrInsert , an instance method in the BinaryTree class. The
function searches the tree for a NodeData item, d . If it is found, it returns a pointer to the node. If it is not found, the
item is inserted in the tree in its appropriate place, and the function returns a pointer to the new node.

public TreeNode findOrInsert(NodeData d) {
if (root == null) return root = new TreeNode(d);
TreeNode curr = root;
int cmp;
while ((cmp = d.compareTo(curr.data)) != 0) {
if (cmp < 0) { //try left
if (curr.left == null) return curr.left = new TreeNode(d);
curr = curr.left;
}
else { //try right
if (curr.right == null) return curr.right = new TreeNode(d);
curr = curr.right;
}
}
//d is in the tree; return pointer to the node
return curr;
} //end findOrInsert

In the while condition, we use the expression d.compareTo(curr.data) . This suggests that we need to write a
compareTo method in the NodeData class to compare two NodeData objects. The method is shown here:

public int compareTo(NodeData d) {
return this.word.compareTo(d.word);
}

It simply calls the compareTo method from the String class since NodeData consists only of a String object. Even
if there were other fields in the class, we could, if we wanted, still decide that two NodeData objects are to be compared
based on the word field or on any other field.

8.7.1 Example: Word Frequency Count
We will illustrate the ideas developed so far by writing a program to do a frequency count of the words in a passage.
We will store the words in a binary search tree. The tree is searched for each incoming word. If the word is not found,