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

Like our linked list node, this node is very simple; it has some public fields and a
few constructors. The node has a field of type int for storing the data contained in this
node and two links of type IntTreeNode for the left and right subtrees. The first con-
structor constructs a leaf node (using null for left and right). The second constructor
is appropriate for a branch node where you want to specify the left and right subtrees.
The node class is not well encapsulated, but as we saw with linked lists, this is
common practice in Java programming. In this chapter, we'll define a tree class that
is well encapsulated and we will make sure that a client of the tree class never sees
these nodes. In the final example of the chapter we will completely hide this node
class by making it a static inner class, as we did with the final version of the linked
list class.
Just as we could reach every node of a linked list by starting at the front and moving
forward, we can reach every node of a binary tree by starting at the overall root and
moving down in the tree. As a result, we need only one field in the tree class: a refer-
ence to the root of the tree:

public class IntTree {
private IntTreeNode overallRoot;
...

}

We purposely use the name overallRoot to distinguish this root from all of the
other roots. There is only one overall root. But each subtree is itself the root of a tree,
and in our recursive methods we'll often use the parameter name root to indicate
any of the roots.
As we did with our linked lists, we'll represent the empty tree by storing the value
null in the overallRoot field:

overallRoot /

17.2 Tree Traversals

We can't do much with our tree class unless we have some way of seeing what's
inside. We want to traverse the tree in such a way that we visit each node exactly
once. There are many different ways to do this. Because the tree is defined recur-
sively, it is easiest to use a recursive approach to this problem. As a result, we want
to traverse the entire left subtree without dealing with any of the elements from the
right and, in a separate operation, traverse the entire right subtree without dealing
with any of the elements from the left. Given this decision, there are three classic
binary tree traversals. Because we read from left to right, we traverse the left subtree
before the right subtree. The question becomes, at what point do you deal with the
root of the tree?