Discrete Mathematics for Computer Science

Rooted Trees 385

In general, if we suppose a binary search tree is built from a list of n randomly ordered

elements. The first element on the list creates the root; the second element creates a left or

right child of the root, depending on whether it is greater than or less than the first element;

and so on. It is possible to prove that the height of such a tree, on average, is O(log 2 (n)).

This bound is independent of any balancing operation.

6.12.3 Tree Traversals

A binary search tree can be built for a sequence of elements by adding the elements

to the tree one by one. For example, consider the sequence D, G, B, F, H, A, E, C.

The elements have a natural linear ordering, the alphabetical ordering, but they do not

appear in alphabetical order in the sequence. The first element, D, becomes the root

of the tree. The next element, G, is greater than D in alphabetical order, so G be-

comes the right child of D. The third element, B, is less than D, so it becomes the

left child of D. The fourth element, F, is greater than D, so it belongs to the sub-

tree rooted at the right child, G, of D. Since F A G and F < G, F becomes the

left child of G. Continuing in this way creates the binary search tree shown in Figure

6.49.

A binary search tree can be traversed in a way that makes it possible to print out

its labels in their proper order. The directed trail in Figure 6.49 shows how this is done.

Traveling along the trail, which starts at the root, output the label of an internal vertex that

has a left child when the vertex is encountered for the second time. Output the labels of

leaves and internal vertices with no left child the first time they are encountered. (Recall

that the root is an internal vertex.) For the tree in Figure 6.49, the labels are encountered

along the trail in the order D, B, A, B, C, B, D, G, F, E, F, G, H, G, D. Following the

procedure will list the letters A, B, C, D, E, F, G, H in alphabetical order.

D

B -G4

B~ .7

3 , 7 8

A C H

5,

E

Figure 6.49 Listing the labels of the vertices. The numbers indicate the order in which

labels are ordered.

There are actually three ways to list the labels at the vertices of a binary tree using the
traversal shown. The listings that result are determined by choosing when to print out the
label at a vertex: before the labels in its subtree, after the labels in its subtree, or between
the labels in its left subtree and the labels in its right subtree. For a nonempty tree T with

root r, left subtree T 1 , and right subtree T2, the formal description of these procedures

follows.