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

If the method has been called with the overall root of the tree as a parameter, then
you expect the recursive calls to return 2 as the number of levels for the left subtree
and 1 as the number of levels for the right subtree. The call on Math.max will cor-
rectly choose the 2 over the 1 for the overall answer, but the overall tree doesn't have
two levels. It has three levels. You have to account for the root node, which is an extra
level, by adding 1 to the previous expression:
private int countLevels(IntTreeNode root) {
if (root == null) {
return 0;
} else {
return 1 + Math.max(countLevels(root.left), countLevels(root.right));
}
}
Without the “ 1 + ” in this expression, the method would always return an answer
of 0 . This is another example of a case in which a minor change in a recursive defini-
tion makes a big difference in how the method behaves.
The height of a binary tree is 1 less than its number of levels. When we count levels,
we say that the empty tree has 0 levels and a tree composed of a single node has 1
level. According to the standard definition of binary tree height, a tree of one node is
considered to have a height of 0 and the empty tree is considered either to have no
height (undefined height) or a height of -1 .
Counting Leaves
As a final example, let's write a method that returns a count of the number of leaf
nodes in a tree. It will have the familiar public/private pair of methods that includes
an initial call with the overall root. You can once again use the recursive definition
of a tree to help you write this code. If a tree is empty, then it has no nodes at all,
let alone any leaf nodes. Thus, you can begin your method with the following lines
of code:
public int countLeaves() {
return countLeaves(overallRoot);
}
private int countLeaves(IntTreeNode root) {
if (root == null) {
return 0;
} else {
...
}
}