Question

In Exercises 7 – 9 determine the order in which a preorder traversal visits the vertices of the given ordered rooted tree.

Short answer

Therefore, the order of pre-order traversal of the given ordered rooted tree is

a, b, e, k, l, m, f, g, n, r, s, c, d, h, o, i, j, p, q.

Step-by-step solution

General form

Pre-order traversal:

Let T be an ordered root tree with root r. If T consists only of r, then r is the pre-order traversalofT. Otherwise, suppose that \({{\bf{T}}_{\bf{1}}}{\bf{,}}{{\bf{T}}_{\bf{2}}}{\bf{,}}...{\bf{,}}{{\bf{T}}_{\bf{n}}}\) are the subtrees at r from left to right in T. The pre-order traversal begins by visiting r. It continues by traversing \({{\bf{T}}_{\bf{1}}}\) in pre-order, then \({{\bf{T}}_{\bf{2}}}\) in pre-order, and so on, until \({{\bf{T}}_{\bf{n}}}\) is traversed in pre-order.

Evaluate the given rooted tree

Given that, the ordered rooted tree.

Determine the order in which pre-order traversal of the given tree.

Let us show the pre-order in an image as shown below.

Case (1):

Case (2):

Case (3):

Case (4):

So, the pre-order traversal of the given ordered rooted tree is a, b, e, k, l, m, f, g, n, r, s, c, d, h, o, i, j, p, q.