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

new value. We reassign overallRoot to this value passed back by add . That way, if
the method changes the value of the parameter, overallRoot gets updated to that
new value. If it doesn't change the value of overallRoot , then we are simply
assigning a variable to the value that it already has (effectively saying " x = x " ),
which has no effect.
Two other calls on add inside the method itself need to be updated in a similar
manner:
private IntTreeNode add(IntTreeNode root, int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value <= root.data) {
root.left = add(root.left, value);
} else {
root.right = add(root.right, value);
}
return root;
}
After we make these changes, the add method works properly.
This x = change(x) idiom is very powerful and simplifies a lot of binary tree
code, so it is important to learn how to use it well.
Searching the Tree
Once we have built a binary search tree, we will want to do more than just printing its
contents or structure. One of the most common operations we might want to perform
is to search the tree to see whether it contains a particular value.
The method to perform this search should return a boolean result and you will
once again want to have a public/private pair of methods, so the basic form of your
solution will be as follows:
public boolean contains(int value) {
return contains(overallRoot, value);
}
private boolean contains(IntTreeNode root, int value) {
...
}
Now you just have to write the body of the private method. An empty tree again
serves as the easy case. If you're asked whether the empty tree contains a value, the
answer is no ( false ):
private boolean contains(IntTreeNode root, int value) {
if (root == null) {