Binary Trees - Building Java Programs: A Back to Basics Approach - page 1006

This program prompts for a series of integers that are added one at a time into the
tree until the user enters the sentinel value 0 . The program then prints the structure of
the tree and the contents of the tree. The following is a sample execution. Notice that
the numbers are printed in increasing order:
Next int (0 to quit)? 42
Next int (0 to quit)? 9
Next int (0 to quit)? 18
Next int (0 to quit)? 55
Next int (0 to quit)? 7
Next int (0 to quit)? 108
Next int (0 to quit)? 4
Next int (0 to quit)? 70
Next int (0 to quit)? 203
Next int (0 to quit)? 15
Next int (0 to quit)? 0
Tree Structure:
203
108
70
55
42
18
15
9
7
4
Sorted list:
4 7 9 15 18 42 55 70 108 203
To begin with, you will need a constructor that constructs an empty tree.
Remember that the empty tree is represented by the value null . In fact you could
simply not have a constructor and Java would provide you with a zero-argument con-
structor that initializes the field overallRoot to null . But it's not a bad idea to
include the constructor anyway for clarity:
public IntSearchTree() {
overallRoot = null;
}
Then you have to write the add method. Because of our data invariant, you can
assume that, each time the method is called, the existing tree is a binary search tree.
You have to make sure that you add the value in an appropriate place so as to pre-
serve the binary search tree property.