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

private int sum(IntTreeNode root) {
...
}
The recursive definition tells us that a tree is either empty or a root node with left
and right subtrees. This definition provides an excellent basis for recursive code. You
know that the empty tree has a sum of 0, so you can begin with that case:
private int sum(IntTreeNode root) {
if (root == null) {
return 0;
} else {
...
}
}
If the tree is not empty, then it is a root node that has left and right subtrees. To
find the sum of the values, you have to combine all three parts: the data stored in the
root node and the sums of the left and right subtrees. This task translates very easily
into recursive code:
private int sum(IntTreeNode root) {
if (root == null) {
return 0;
} else {
return root.data + sum(root.left) + sum(root.right);
}
}
Counting Levels
As a second example, let's write a method called countLevels that returns the
number of levels in a tree. For our purposes, we consider the root node to be at
level 1 , its children to be at level 2 , its grandchildren to be at level 3 , and so on.
The countLevels method should return the level of the node that is furthest from
the root.
You can again solve this task by writing a public/private pair of methods. The
public method returns the result of invoking the private method with the overall
root:
public int countLevels() {
return countLevels(overallRoot);
}