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

This is the general structure that you want, but exactly how do you add to the left
or right subtree? Some novices try to test things about the left or right subtree, as in
the following example:
// overly complex version
private void add(IntTreeNode root, int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value <= root.data) {
if (root.left == null) {
root.left = new IntTreeNode(value);
} else {
// even more stuff
}
} else {
// add to right
}
}
This is not a good way to approach the problem. If you're thinking recursively,
you'll realize that it's another insertion task into either the left or the right subtree.
You can call the add method itself:
// simpler, but does not quite work
private void add(IntTreeNode root, int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value <= root.data) {
add(root.left, value);
} else {
add(root.right, value);
}
}
The logic of this code is almost correct. Unfortunately, in this form the tree always
remains empty. The add method never inserts a value. The problem has to do with
the parameter called root . The parameter root will store a copy of whatever value is
passed into it. As a result, when you reassign root , it has no effect on the value that
is passed into it.
There is a particular approach to solving this problem that is very helpful in writing
binary tree code. Let's explore this issue and the technique in some detail before we
try to fix this code.