Traversal

There are several ways to traverse the nodes in a tree data structure, but which one you choose will be based largely on how the nodes of your tree are implemented. For example, our Node class includes references from parents to children, but not the reverse. Nor does it provide references to any siblings or cousins of the same order, or level, of the tree. Therefore, our traversal pattern is limited to stepping through the tree by means of following edges, or references, from parents to children. This type of traversal is called walking the tree.

Our node construction would have also allowed us to examine either child prior to examining the parent. If we had structured our search patterns to check the left child node, then the right child node, and finally the node itself, we would have implemented an in-order traversal. If our nodes contained links between objects of the same order, we could examine all parents of a particular order prior to examining any children. This approach...