ABSTRACT
The structure of trees is naturally recursive. When trees are used as data structures,
they are typically processed by recursive procedures. Similarly, exhaustive search
programs working by recursion also construct trees as they follow their search paths.
These trees are always rooted trees; that is, they begin at a distinguished node, called
the root vertex, and are usually built outwards from the root. Figure 6.1 shows several
rooted trees, where the root vertex is shaded black.