Discrete Mathematics for Computer Science

Rooted Trees 387

To carry out a preorder or a postorder listing, follow the same trail alongside the tree.

For a preorder listing, however, record the label on the vertex the first time the vertex is

encountered. For a postorder listing, record the label on the vertex the last time it is passed,

as the traversal moves up to the vertex's parent. Examples of these listings of the labels

are shown in Figure 6.51. Notice that for preorder and postorder listing, the labels at the

vertices are not listed in alphabetical order.

Postorder Preorder

milk milk

"c"soda " "soda

cereal• 8 7, cere
a
6
l milkl 8

banana" gape b\ grape

3 5 6 banana

1 /, orange water 3 / orange water

fruit 2 fruit^5

banana milk

fruit cereal

grape banana

cereal grape

orange fruit

water soda

soda orange

milk water

Figure 6.51 Tree traversals.

6.12.4 Application: Decision Trees

To find a lower bound for the complexity of a class of algorithms, it is necessary to find
a model for all possible algorithms of the class. The lower bound for sorting algorithms
based on using a comparison of two elements as the fundamental operation can be found
by using a decision tree model. A decision tree is a rooted binary tree with labeled vertices
and edges.
Each step of a comparison-based sorting algorithm involves the comparison of two
distinct elements (if two elements were the same, we would be reduced to a smaller case)
using the linear order on the set of elements being sorted. These comparisons are used to
label the vertices of the tree. The label a : b at a vertex indicates that a and b are to be
compared. The left edge from a vertex represents what is known about the order of the
elements when a < b is true. The right edge represents what is known about the order of
the elements when b < a is true. Each leaf represents the fact that the questions used to
get to that leaf have completely identified the order among the elements of the input. The
discovered order is then presented in a box. Figure 6.52 shows a tree that represents one
way to sort three elements.