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

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

figure 18.21
A routine for
computing the height
of a node

tree traversal: iterator classes

18.4

In this chapter we have shown how recursion can be used to implement the
binary tree methods. When recursion is applied, we compute information
about not only a node but also about all its descendants. We say then that we
are traversing the tree . Two popular traversals that we have already mentioned
are the preorder and postorder traversals.
In a preorder traversal, the node is processed and then its children are pro-
cessed recursively. The duplicate routine is an example of a preorder traversal
because the root is created first. Then a left subtree is copied recursively, fol-
lowed by copying the right subtree.
In a postorder traversal, the node is processed after both children are pro-
cessed recursively. Two examples are the methods size and height . In both
cases, information about a node (e.g., its size or height) can be obtained only
after the corresponding information is known for its children.

A third common recursive traversal is the inorder traversal, in which the
left child is recursively processed, the current node is processed, and the right
child is recursively processed. This mechanism is used to generate an alge-
braic expression corresponding to an expression tree. For example, in
Figure 18.11 the inorder traversal yields (a+((b-c)*d)) .

In an inorder tra-
versal , the current
node is processed
between recursive
calls.

Figure 18.22 illustrates routines that print the nodes in a binary tree using
each of the three recursive tree traversal algorithms. Figure 18.23 shows the
order in which nodes are visited for each of the three strategies. The running
time of each algorithm is linear. In every case, each node is output only once.
Consequently, the total cost of an output statement over any traversal is O ( N ).
As a result, each if statement is also executed at most once per node, for a
total cost of O ( N ) . The total number of method calls made (which involves
the constant work of the internal run-time stack pushes and pops) is likewise
once per node, or O ( N ) . Thus the total running time is O ( N ).

Simple traversal
using any of these
strategies takes lin-
ear time.