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

return false;
}
...
}
For the add method, you had two other cases. You either added to the left subtree
or added to the right subtree. For this method, there are three cases, cases for search-
ing the left and right subtree and the root:
private boolean contains(IntTreeNode root, int value) {
if (root == null) {
return false;
} else if (value == root.data) {
...
} else if (value < root.data) {
...
} else { // value > root.data
...
}
}
Now you just need to fill in the three different cases. If the value is less than
root.data , then it is either in the left subtree or not in the tree at all. In other words,
you want to search the left subtree to see whether it contains the value. You can
accomplish this with a recursive call on contains . You can make a similar recursive
call on contains to search the right subtree when the value is greater than
root.data . In the final case in which the value is equal to root.data , you should
simply report that you found the value. In other words, the answer is true . Putting
these pieces together, you end up with the following code:
private boolean contains(IntTreeNode root, int value) {
if (root == null) {
return false;
} else if (value == root.data) {
return true;
} else if (value < root.data) {
return contains(root.left, value);
} else { // value > root.data
return contains(root.right, value);
}
}