Trees - Data Structures and Problem Solving Using Java - page 666

1 /**
2 * Return the size of the binary tree rooted at t.
3 */
4 public static <AnyType> int size( BinaryNode<AnyType> t )
5 {
6 if( t == null )
7 return 0;
8 else
9 return 1 + size( t.left ) + size( t.right );
10 }

figure 18.19
A routine for
computing the size of
a node

subtree plus 1 (because the root counts as a node). A recursive routine
requires a base case that can be solved without recursion. The smallest tree
that size might have to handle is the empty tree (if t is null ), and the size of an
empty tree is clearly 0. We should verify that the recursion produces the cor-
rect answer for a tree of size 1. Doing so is easy, and the recursive routine is
implemented as shown in Figure 18.19.
The final recursive routine presented in this section calculates the height
of a node. Implementing this routine is difficult to do nonrecursively but is
trivial recursively, once we have made a drawing. Figure 18.20 shows a tree
viewed recursively. Suppose that the left subtree has height H L and the right
subtree has height H R . Any node that is d levels deep with respect to the root
of the left subtree is levels deep with respect to the root of the entire tree.
The same holds for the right subtree. Thus the path length of the deepest node
in the original tree is 1 more than its path length with respect to the root of its
subtree. If we compute this value for both subtrees, the maximum of these two
values plus 1 is the answer we want. The code for doing so is shown in
Figure 18.21.

The height routine
is also easily imple-
mented recursively.
The height of an
empty tree is -1.

d + 1

H R +1

H L +1

H R

H L

figure 18.20
Recursive view of the node height calculation:
H T = Max ( H L + 1, H R + 1)