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

The add method will have the usual structure of a public method that the client
calls with no mention of tree nodes and a private recursive method that takes a node
as a parameter and that does the actual work. Thus, your pair of methods will look
like this:
public void add(int value) {
add(overallRoot, value);
}
private void add(IntTreeNode root, int value) {
...
}
Recall that a binary tree is either empty or a root node with left and right subtrees.
If it is empty, then you want to insert the value here. For example, initially the overall
tree is empty and you insert the first value at the top of the tree (replacing the null
value with a reference to a new leaf node that contains the given value). So the
private add method would start like this:
private void add(IntTreeNode root, int value) {
if (root == null) {
root = new IntTreeNode(value);
}
...
}
But what if it's not an empty tree? Then it must have a root node with some
data. Let's assume that duplicates are allowed, so that you want to insert this value
no matter what. In the case in which root is not null , you know that the new
value has to be added to one of the subtrees. Which one? You can compare
the value you are inserting to the data in the root to figure that out. If the value is
less than or equal to the root's data, then you insert the value into the left subtree;
otherwise, you insert into the right subtree. Your method will look something
like this:
private void add(IntTreeNode root, int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value <= root.data) {
// add to left
} else {
// add to right
}
}