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

Notice that in the public method you need to pass the value 1 to indicate that the
first call should be generating a tree with 1 as its root value. And as the comments
indicate, you only want to construct the tree if the value of n is less than or equal to
the value of max .
The requirement that you want to stop building the tree for values of n that are
greater than max gives you an appropriate base case for the private method:

private IntTreeNode buildTree(int n, int max) {
if (n > max) {
return null;
} else {
...

}

}

Now you just have to fill in the recursive case. You know that you need to con-
struct a node that stores the value n . The less obvious part is how to construct the left
and right subtrees. For the moment, you can introduce some local variables for the
two subtrees; later, you will fill in the details about how to construct them. The
method so far looks like this:

private IntTreeNode buildTree(int n, int max) {
if (n > max) {
return null;
} else {
IntTreeNode left = ...
IntTreeNode right = ...
return new IntTreeNode(n, left, right);

}

}

We suggested building this particular tree because there is a simple mathematical
relationship between each node in this tree and its children. If a node is numbered n ,
then its left child is numbered 2 n and its right child is numbered 2 n 1. For exam-

ple, the overall root is numbered 1 and its children are numbered 2 and 3 . The left
subtree is numbered 2 and its children are numbered 4 and 5 , and so on.
Getting back to our code, now that we know what value to store in each of the two
children, we can use recursive calls to construct the left and right subtrees:

private IntTreeNode buildTree(int n, int max) {
if (n > max) {
return null;
} else {