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

recursion and trees

18.3

Because trees can be defined recursively, many tree routines, not surprisingly,
are most easily implemented by using recursion. Recursive implementations
for almost all the remaining BinaryNode and BinaryTree methods are provided
here. The resulting routines are amazingly compact.

Recursive routines
are used for size
and duplicate .

We begin with the duplicate method of the BinaryNode class. Because it is
a BinaryNode method, we are assured that the tree we are duplicating is not
empty. The recursive algorithm is then simple. First, we create a new node
with the same data field as the current root. Then we attach a left tree by call-
ing duplicate recursively and attach a right tree by calling duplicate recur-
sively. In both cases, we make the recursive call after verifying that there is a
tree to copy. This description is coded verbatim in Figure 18.17.

Because duplicate
is a BinaryNode
method, we make
recursive calls only
after verifying that
the subtrees are
not null .

The next method we write is the size routine in the BinaryNode class. It
returns the size of the tree rooted at a node referenced by t , which is passed as
a parameter. If we draw the tree recursively, as shown in Figure 18.18, we see
that the size of a tree is the size of the left subtree plus the size of the right

The size routine is
easily implemented
recursively after a
drawing is made.

1 /**
2 * Return a reference to a node that is the root of a
3 * duplicate of the binary tree rooted at the current node.
4 */
5 public BinaryNode<AnyType> duplicate( )
6 {
7 BinaryNode<AnyType> root =
8 new BinaryNode<AnyType>( element, null, null );
9
10 if( left != null ) // If there's a left subtree
11 root.left = left.duplicate( ); // Duplicate; attach
12 if( right != null ) // If there's a right subtree
13 root.right = right.duplicate( ); // Duplicate; attach
14 return root; // Return resulting tree
15 }

figure 18.17
A routine for returning
a copy of the tree
rooted at the current
node

figure 18.18
Recursive view used
to calculate the size of
a tree:
S T = S L + S R + 1 .

S L S R